**Binary Search Algorithm**

Binary search algorithm is algorithm which divides input into two halves and based on relation between key and middle element, discards one half and carry forward with remaining other part. With each divide, input reduces by half. This algorithm works sorted set of input.

For example, A is an array as {1,3,5,6,7,8, 9} and let’s say we need to find key 5 in this array. It takes linear time by scanning each element, worst case time complexity of O(N) when the element to be search is last element of array. Can we do better? Yes, as we can see input array is sorted, it is best case to use binary search algorithm.

** Binary search algorithm : Analysis **

First find middle of input array. Check if middle element is equal to key we are looking for, if yes, key found at middle index. If element at middle index is less than key, key is in right part of array. Why? On the other hand, if middle element greater than key, then key is in left part of array. So in any case, we discard other half and focus on remaining half. We apply same steps on remaining subarray till either we get the key or we cannot further split array (when subarray has only one element). Below is summary of what we just discussed.

1. Find middle of input array. 2. Check if element at middle index is equal to key, return middle 3. If middle is equal to start and element at middle is not equal to key, return "Element not present" 4. If element at middle index is greater than key, change end of array as one index lower than middle and go to step 1. 5. If element at middle index is less than key, change start of array as one index higher than middle and go to step 1.

Let’s see how binary search algorithm works with an example:

Given array is : A = [4,9,25,28,29,34,45,50,67,70] and key to be searched is 35.

First step is to find middle of array. In this case, middle element is 34.

Since middle element 34, is less that 35, we know that all elements at indices less than middle including middle are less than our key. Why? Because we know that input array is sorted array. Hence, we will discard subarray from 0 to mid.

Now, new array to be searched is from mid+1 to end. Find middle to new array, it will be index 7 (50) now.

Since element at middle index is greater than key looking for, we can safely discard array starting from mid to end as all elements at indices greater than middle, including middle will be greater than key.

Now, we are left with an array with one element, in this case start and end will be equal and hence, middle will be same index. Check if element at middle is equal to key. If yes, return index, In this example, yes, it is equal and we will return middle index. If middle index element is not equal to key, in next iteration, start <= end condition will not be true in any case, hence recursion will terminate.

### Recursive implementation of binary search algorithm

###
#include <stdio.h>
int binarySearch(int a[], int start, int end, int key){
if(start <= end) {
int mid = (start + end)/2;
if(a[mid] == key) return mid;
if(a[mid] < key)
return binarySearch(a, mid+1, end, key) ;
else
return binarySearch(a, start, mid-1, key) ;
}
return -1;
}
int main(void) {
int a [] = {1,2,3,4,5,6,7,8};
int size = sizeof(a)/sizeof(a[0]);
printf("Element found at : %d", binarySearch(a, 0, size, 4));
return 0;
}

Recursive implementation in python

def binarySearch(array, item): if len(array) == 0: return -1 else: mid = len(array)//2 if array[mid]==item: return mid else: if item < array[mid]: return binarySearch(array[:mid],item) else: return binarySearch(array[mid+1:],item) test_array = [0, 1, 2, 8, 13, 17, 19, 32, 42,] print "Element found at :" print(binarySearch(test_array, 3)) print "Element found at :" print(binarySearch(test_array, 13))

### Iterative implementation of binary search algorithm

###
#include <stdio.h>
int binarySearch(int a[], int start, int end, int key){
while(start <= end){
int mid = (start + end)/2;
if(a[mid] == key) return mid;
if(a[mid] < key)
start = mid+1;
else
end = mid-1 ;
}
return -1;
}
int main(void) {
int a [] = {1,2,3,4,5,6,7,8};
int size = sizeof(a)/sizeof(a[0]);
printf("Element found at : %d", binarySearch(a, 0, size, 4));
return 0;
}

Python implementation of binary search algorithm

def binarySearch(alist, item): first = 0 last = len(alist)-1 found = -1 while first<=last and found == -1: midpoint = (first + last)//2 if alist[midpoint] == item: found = midpoint else: if item < alist[midpoint]: last = midpoint-1 else: first = midpoint+1 return found testlist = [0, 1, 2, 8, 13, 17, 19, 32, 42,] print " \nElement found at :" print binarySearch(testlist, 3) print " \nElement found at :" print(binarySearch(testlist, 13))

**Execution of binary search implementation**

Following execution traces are give for following array A = [1,2,3,5,7,8,9,10]

Positive case (Search for 5)5 is less than 7 Moving to left part 5 is greater than 2 Moving to right part 5 is greater than 3 Moving to right part Element located at 3 index

Negative case (Search for 6)6 is less than 7 Moving to left part 6 is greater than 2 Moving to right part 6 is greater than 3 Moving to right part Element not present in input

With each comparison, search space reduces to half. How many comparisons required to either find an element or decisively say that it does not exist in array? We start with n elements, with first comparison, search space reduces to n/2, with second comparison, it reduces to n/4 and so on. It can be easily proved with Master’s theorem binary search algorithm has complexity of **O(LogN)**. Recursive implementation of binary search algorithm has space complexity of O(log n).

Python implementation has some hidden complexities, like we use slice operation on array which is passed to next invocations. This operation is not constant time and hence python implementation is not strictly logarithmic. Apart from this, slice returns a new array each time and hence we are adding to space complexity too. These problems can be easily solved, by passing the original array in each invocation along with start and end index to be searched on in array.

Recently, I found an article on Google Research blog which has a very good point to keep in mind while coding binary search algorithm. Have a look : Google Research blog

In next post i would discuss some more problems related to binary search like finding no of instances of an element, first instance of an element, closest element to a key in an array etc.

Please share if there is something wrong or missing. If you are interested in contributing to algorithms and me, please contact us.

Pingback: First occurrence of number in sorted array - Algorithms and Me()

Pingback: Last occurrence of number in sorted array - Algorithms and Me()

Pingback: Amazon interview experience analysis | Set 1 - Algorithms and Me()