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-**

for(i=0;i<N;i++) { if(arr[i]==key) { printf("Element is found\n");break; } }

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-

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); } }

**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)).