Binary Search

Linear search (searching each index in an array one by one) works almost everywhere but it is not optimal in many cases. Let's assume, we have a book which has 42949672960 pages. We also have a table of contents. Now we want to read the content on page 104000. How do we do that? Go to every page one by one? No, linear search would take multiple days to do that. For simplicity, let’s assume there are 18 pages in the book and we want to find out the content of page 16. Then we will go back to how binary search is very fast and efficient for a gigantic search space.

  page numbers ->   1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 
At first, we divide the book into two equal parts and find middle value which is (1 + 18) / 2 or 9 (we are taking floor value of 9.5). First part has page 1 to 9, second part has page 10 to 18. We can definitely tell that first part does not have our target page because the highest page which is 9 is less than 16. So, we eliminate that part.

page numbers ->    1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 
Now, we have page 10 to 18 to search. Let’s divide it again, middle value is (10 + 18) / 2 or 14. First part has page 10 to14, second part has page 15 to 18. Again, eliminate the first part as 16 is in the range of 15 to 18. We repeat this procedure until we get a middle value which is equal to our target value 16.

page numbers ->  10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 |  
Current search space is 15 to 18, mid = (15 + 18) / 2 or 16, which is our target value. So, we stop here. One thing to keep in mind that binary search works only for sorted sequence items where we eliminate our search space based on their median and target value. Here is a coding example for binear search implemented in Java.   

// getKeyIteratively() takes 2 parameters
                      // 1. array of pages 2. target value
                      // Returns the index of target value/key
                      // If target value is not found, it returns -1
                      public int getKeyIteratively(int[] pages, int key) 
                      {
                      	int length = pages.length;
                      	int lo = 0, hi = length - 1;
                      	while(lo <= hi) 
                      	{
                      		int mid = (lo + hi)/2;
                      		// if value is target value
                      		if(pages[mid] == key) return mid;
                      		else if(key < pages[mid]) hi = mid - 1;
                      		else lo = mid + 1;
                      	}
                      	// key not found
                      	return -1; 
                      }
                      

Select all Open in new window

Complexity
Each comparison divides the array into two parts and considers only one half. This makes our search space half of the previous search space. That is why, it is gaurenteed to find a solution in O(lgN) comparison (if there is a solution) in an array of N items. Going back to  2^32 or 42949672960 pages we would have to perform at most 2^32 comparisons to find our result using linear search. In case of binary search we would need only lg(2^32) or 32 comparisons which is a very small number compared to 2^32.