# Binary Search

Published:
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
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;
}