Binary Search in c

Binary search is a searching algorithm that works on the principle of divide and conquer. The time complexity of this searching technique is

O (log N). The target array given must be sorted for this algorithm to work. This algorithm can be implemented by two methods, either iterative or recursively.

How does binary search work?

Binary search is used to find a target value (item to be found) by reducing the search space with every iteration. Initially, the search space is the entire sequence. Binary search compares the target value to the middle element of the search space and because the array is sorted it decides whether the target lies to the left or the right of the middle value. In some cases, the middle value may be the target value. Once this decision is made the search space is reduced to half and all the other elements are eliminated. This process goes on until either the value is found or the search space is left with only one element.

Consider the example, where the element to be found is 35

5 12 17 18 19 20 26 33 35 47
0 1 2 3 4 5 6 7 8 9

mid

Initially, the middle index is found by the formula

mid = low + (high – low)/2

In this case, the mid is 0 + (9-0)/2 = 4.5

In the case where mid index is a floating-point number, the floor value (the lowest integer closest to the value) is considered. Now the target value is compared to the value at the middle index. As 35>19 it must be on the right of it, thus all the elements to the left of 19 are eliminated and the search space is reduced as depicted below.

5 12 17 18 19 20 26 33 35 47

0 1 2 3 4 5 6 7 8 9

eliminated elements

mid

Now the low is changed to mid + 1 and again mid is calculated using the same formula

Thus mid = 5+(9-5)/2 = 7

We again find 35>33 thus the left elements are eliminated again and the search space is reduced to only two elements

5 12 17 18 19 20 26 33 35 47

0 1 2 3 4 5 6 7 8 9

The low value is again changed to mid + 1 and the mid is recalculated as

mid = 8+(9-8)/2 = 8

As the value of the middle index is equal to the target value the search stops and we find our result at index 8. Thus, the resultant index is the output of the search.

ALGORITHM

A ← sorted array
n ← size of array
x ← value to be searched
Set first = 0
Set last = n - 1
while x not found
if last < first
EXIT: x does not exist.
set mid = first + (last - first) / 2
if A[mid] < x
set first = mid + 1
if A[mid] > x
set last = mid - 1
if A[mid] = x
EXIT: x found at location mid
end while

C++ CODE FOR ITERATIVE BINARY SEARCH

#include<iostream>
using namespace std;

int BinarySearch(int f, int l, int *a, int item) {
while(f<=l) {
int mid=(f+l)/2;
if(a[mid]==item) {
return mid;
}

else if(a[mid]>item) {
l=mid-1;
}
else {
f=mid+1;
}
}
return -1;
}

int main() {
int* a=NULL;
int n, i, j, item;
cout<<"Enter the number of elements: ";
cin>>n;
a = new int[n];
cout<<"Enter the elements: ";
for(i=0;i<n;i++) {
cin>>a[i];
}
cout<<"Enter the element you wish to search: ";
cin>>item;
int x = BinarySearch (0, n-1, a, item);
cout<<"The value is found at index "<<x;
return 0;
}

The output of the code is:

Iterative Binary Search Output

The only constraint is that the input array must be sorted.

NOTE:

Some might use the formula

mid = (low + high)/2 to calculate the middle index but this might result in overflow and to avoid such errors mid = low + (high – low)/2 must be used.

For example, the signed int in C/C++ generally use 4 bytes of storage, i.e., it allows storage for integers between -2147483648 to 2147483648. So, if (low + high) > 2147483648, integer overflow will happen. Thus, using this formula should be avoided for very large values.

C++ CODE FOR RECURSIVE BINARY SEARCH

#include<iostream>
using namespace std;

int binarySearch(int *arr, int l, int r, int x) {
while (l <= r) {
int m = l + (r - l) / 2;
if (arr[m] == x)
return m;
if (arr[m] < x)
l = m + 1;
else
r = m - 1;
}
return -1;
}

int main() {
int* a = NULL;
int n, i, j, item;
cout<<"Enter the number of elements: ";
cin>>n;
a = new int[n];
cout<<"Enter the elements: ";
for(i=0;i<n;i++) {
cin>>a[i];
}
cout<<"Enter the element you wish to search: ";
cin>>item;
int x = binarySearch(a, 0, n-1, item);
cout<<"The value is found at index "<<x;
return 0;
}

The output of the code is:

Recursive Binary Search Output

 

Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments