<

Binary Search

Published on
3,801 Points
701 Views
1 Endorsement
Last Modified:
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; 
}

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.
 
1
Comment
0 Comments

Featured Post

Free Tool: IP Lookup

Get more info about an IP address or domain name, such as organization, abuse contacts and geolocation.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Join & Write a Comment

I've attached the XLSM Excel spreadsheet I used in the video and also text files containing the macros used below. https://filedb.experts-exchange.com/incoming/2017/03_w12/1151775/Permutations.txt https://filedb.experts-exchange.com/incoming/201…
In a question here at Experts Exchange (https://www.experts-exchange.com/questions/29062564/Adobe-acrobat-reader-DC.html), a member asked how to create a signature in Adobe Acrobat Reader DC (the free Reader product, not the paid, full Acrobat produ…
Suggested Courses
Next Article:

Keep in touch with Experts Exchange

Tech news and trends delivered to your inbox every month