This is a short note on using binary search, in continuance of my series on Algorithms.

Suppose we have to find whether a particular element exists in the sorted list of N numbers or not.

Let “arr” be the array which contains the N elements and the element to be searched is “key”.

Then, the time complexity using brute force will be O(N).

**CODE-**

[cpp]

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

{

if(arr[i]==key)

{

printf("Element is found\n");break;

}

}

[/cpp]

But,using binary search,the time complexity will be O(log(N)).A binary search halves the number of items to be checked each time and thus has logarithmic complexity.

**ALGORITHM-**

In this algorithm,the key is compared with the middle element of the array.

Cases:

1.If the middle element is equal to the key,then the search is completed.

2.If the key is less than the middle element,then the algorithm is repeated on the sub-array to the left of the middle element.

3.If the key is greater than the middle element,then the algorithm is repeated on the sub-array to the right of the middle element.

4.If the remaining array to be searched is empty,then the key cannot be found in the array and the search is completed.

**CODE-**

Recursive solution-

[cpp]

int binarysearch(int arr[],int key,int beg,int last)

{

// beg and last indicate the starting and ending indices of the subarray.

// Initially,beg has the value 0 and last has the value n-1.</em>

if(beg >last) return 0; // key not found</em>

else

{

int mid=(beg+last)/2; // finding the middle element</em>

if(key==arr[mid])return 1; // key found</em>

else if(key < arr[mid]) return binarysearch(arr,key,beg,mid-1);

else

return binarysearch(arr,key,mid+1,last);

}

}

[/cpp]

**NOTE-** Binary Search is used only when the given list is sorted.If the list is unordered,brute force is better as sorting will have a complexity of O(N*log(N)).