Binary Search Program in C (Recursive & Iterative)

Last updated Dec 11, 2020

Binary Search Program in C (Recursive & Iterative)- If you are a programmer then you must know about c programming language. We do programming in c to find the exact position of the element. Today we will know a brief about binary search in c that makes our programming easy and fun. Let's get started.

What is a Binary search?

A binary search is usually a search algorithm that helps in finding the exact position of the element using a short line of codes. It is also known as a half interval search, as we select or eliminate the half. This search runs in logarithmic time. Let's see how binary search in c works.

How binary search in C works?

There is some condition to use a binary search:

The array should be sorted to apply binary search.
If the selected target is equal to the middle element, binary search ends.

Case 1 − If element = middle, hence we found the element, return the index.

Case 2 − If element > middle, then search for the sub-array element starting from (middle+1) and index it to (n).

Case 3 − If element < middle, then search for the sub-array element starting from (0) index to middle (-1).

It usually compares the target value with the middle element of the array.
If they are not the same, eliminate the half in which the selected target is not present and continue the search on the remaining half.
From the remaining half again take the middle element to compare with the target value.
Repeat the above steps until the target value is not found. Binary search is completed.

Algorithm

We will use two parameters for the binary search program in c i.e i_value (initial value), e_value (end value).

Step 1- To find the middle element of a sorted array by using
middle_element = i_value + e_value / 2
Step 2- If middle element = element then return ‘element found’ and index it.
Step 3- if middle_element > element then call the function with e_value = middle_element - 1.
Step 4- if middle_element < element, then call the function with start_value = middle_element + 1.
Step 5- Stop.

The Binary search algorithm uses call to function again and again. These call functions can be of two types-

Iterative- Iterative function creates loops over the same block of codes multiple times in the program. Some C iteration statements are for, while, do while, etc.
Recursive- Recursive function is the process of repeating items within a self-similar method. In programming languages, even when a program gives you the ability to call a function within an identical function, then it's called a recursive call of this function. In short, calling one function again and again is a recursive function.

Binary Search Program in C Using Iterative Call

Algorithm-

Step 1- Input the sorted array as an int. Take 2 variables last_index and start_index.
Step 2- If start_index <= last_index return middle_index.
Step 3- Make an iterative function. If array[middle] = element return 'middle', if array[middle] < element return start_index = middle+1,
else return last_index = middle-1.
Step 4- If found_index = -1 return 'element not found'
else return 'Element found at: found_index'.
Step 5- Stop

Example

#include
int iterativeBSearch(int array[], int start_index, int last_index, int element){
while (start_index <= last_index){
int middle = start_index + (last_index- start_index )/2;
if (array[middle] == element)
return middle;
if (array[middle] < element)
start_index = middle + 1;
else
last_index = middle - 1;
}
return -1;
}
int main(void){
int array[] = {2, 6, 8, 7, 26, 38, 45};
int n = 7;
int element = 38;
int found_index = iterativeBSearch(array, 0, n-1, element);
if(found_index == -1 ) {
printf("Element not found in this array ");
}
else {
printf("Element found at: %d",found_index);
}
return 0;
}

Output:

Element Found at: 5

Binary Search Program in C Using Recursive Call

Algorithm-

Step 1- Input the sorted array as an integer. Take 2 variables last_index and start_index.
Step 2- If last_index >= start_index return middle_index.
Step 3- Make a recursive function that will call itself and
return the recursive call function to (array, start_index, middle-1) + (array, middle+1, last_index).
Step 4- If found_index = -1 return 'element not found'
else return 'Element found at: found_index'.
Step 5- Stop

#include
int RecursiveBSearch(int array[], int start_index, int last_index, int element){
if (last_index >= start_index){
int middle = start_index + (last_index - start_index )/2;
if (array[middle] == element)
return middle;
if (array[middle] > element)
return RecursiveBSearch(array, start_index, middle-1, element);
return RecursiveBSearch(array, middle+1, last_index, element);
}
return -1;
}
int main(void){
int array[] = {2, 8, 17, 49, 26, 36, 21};
int n = 49;
int element = 36;
int found_index = RecursiveBSearch(array, 0, n-1, element);
if(found_index == -1 ) {
printf("Element not found ");
}
else {
printf("Element found at: %d",found_index);
}
return 0;
}

Output:

Element Found at: 5

Performance of Binary search algorithm

In each step of the binary search algorithm our search reduces to half. It means that if our space contains n elements then after one iteration it will become n/2 and then n/4.....so on. The best case in the binary search is when the desired element is equal to the middle one.

The time complexity of binary search algorithms is O(log n). For the best case it would be O(1), when the centered element is equal to desired value.

Efficiency of Binary search

Binary search algorithm is an efficient algorithm used to find an element from the sorted list and takes minimum time to search an element. It is more efficient and faster as compared to linear search.

Conclusion

Binary search is a fast and efficient algorithm to find an element from the sorted array. It takes minimum time to search an element as compared to linear search. There are two calls to function which are important in binary search algorithms in c, Iterative & recursive function. The given program above is a binary search algorithm in C for recursive and iterative both

Tags:

Binary search in C, binary search program in C

Article Contributed By :

1359 Views

Projects By category