Given an array of numbers, how do you search for a number?

The simplest method is to start at the first element and keep comparing until the end of the array. If it is found anywhere in the middle, return it. Otherwise we would reach the end of the array which indicates that the element in not found in the array. This is called linear search. Since this algorithm examines all the elements in the worst case, it’s time complexity is O(n).**Binary search** on the other hand runs in O(log n) which is better compared to linear search. Binary search requires the **input array to be sorted**.

Binary search starts by dividing the array in two halves. Then we compare the search element with the middle element, if it matches, we return that index. If the middle element is less than the search element, then we can ignore the left half of the array because all the elements which precede middle are far away from the search element. Hence we can confine our search to the right half only. Similarly if the middle element is greater than the search element, no need to search the right half. We can confine our search to the left half only. The same procedure is repeated until we find the element or, the array size becomes 1.

Let us look at an example to understand this algorithm

Let us consider the input array as [1,2,3,4,5,6,7,8,9] and we want to search for 6. Here is how the algorithm works

step 1: [1,2,3,4,(5),6,7,8,9] – middle element is 5 which is less than 6. So skipping the left half

step 2: [6,(7),8,9] – middle element is 7 which is greater than 6. So skipping right half

step 3: [6] – middle element is 6. match found, so return it.

#include <iostream>

using namespace std;

int array[100];

//takes the following parameters

`//s: search element, lower index, higher index`

int bin_search(int s, int low, int high)

{

while( low <= high)

{

// the middle element

int middle = (low + high)/2;

//if match is found, return it

if( array[middle] == s)

return middle;

//if middle element is less

else if ( array[middle] < s)

{

//search the right half

low = middle+1;

}

else

{

//search the left half

high = middle-1;

}

}

return -1;

}

int main()

{

int n; // array size

cin>>n;

int i;

for( i = 0 ; i < n ; i++)

{

cin>>array[i];

}

//search element

int s;

cin>>s;

cout<<s<<" found at: "<<bin_search(s,0,n-1);

return 0;

}