Binary Search Algorithm

Finding Contact from Telephone Directory

                What will you do, if you have to find out contact number in an old fashioned Telephone Directory? 

One thing you might do is flipping pages from beginning until you reach the page with Contact name starting with the First letter of your query. This method takes fewer efforts if you want to find out contact with Initial from starting alphabets of the alphabetical order. The same method takes more flipping of pages if you want to find out contact with Initial from last letters of alphabets of the alphabetical order.

Another easy and more accepted method than former is to open Telephone Directory at the middle
and check out current page. If it contains query’s Initial letter, then search complete. If it contains contacts with initial before query’s initial, then Second half of the directory remains to search Else First half of the Directory search. Then you go through the same process opening the middle of remaining Searchable Directory until you complete your search. This method is more efficient than first regardless of Query’s initial. If we cannot have the query, has to choose one of the methods Then this is better than the former one.

Other Searching Cases 

Suppose, you have one of those big books (let’s say 1000 pages long). Unfortunately, you forgot your book at home on the table and your Dog chewed some of the pages. Now you want to check whether page no. 345 is intact or chewed out. Another case is that I think of a number from 1 to 100 and you have to guess it in minimum chances. Each time you guess a number, I would reply to go lower or go higher and once you guess the number correctly the guesses that it took you reach it will be counted. In this both cases you can apply above two methods to find out the answer. You can go sequentially or You can eliminate half possibilities at the time. 

 Linear Search And Binary Search

Above mention, the First method of search in a sequence is called Linear Search. Second Method of each time eliminate half possibilities is called Binary Search. Binary search has restrictions on some cases. You cannot perform the binary search on randomly organized elements. Binary search can be performed on any range of data in which result has borderline of its after elements and before elements.

Now, when we understood what is binary search we can implement it in any Programming Language. I demonstrate implementation of searching integer in array of integers by both ways linear Search and Binary Search in C/C++.

Linear Search

	/*Linear Search Function
	Time Complexity : O(N)
	Space Complexity : O(1)
	*/
	int Linear_Search(int data_array[],int SizeOf_data_array,int Query_Element)
	{
	int Index;
	//Loop for traversing Array
	for(Index=0;Index<SizeOf_data_array;Index++)
	if(data_array[Index]==Query_Element)
	return Index;//return Index of Query_Element
	//return -1 if not found Query_Element
	return -1;
	}

view raw Linear_Search.cpp hosted with ❤ by GitHub

Binary Search

	/*Binary Search Function
	Time Complexity : O(log2 N)
	Space Complexity : O(1)
	*/
	int Binary_Search(int data_array[],int SizeOf_data_array,int Query_Element)
	{
	//intially we have to check all Array
	int First_Index = 0;
	int Last_Index = SizeOf_data_array-1;
	//Looping of same process untill we hit element
	while(First_Index < Last_Index)
	{
	int Mid_Index=(First_Index + Last_Index)/2;
	if(data_array[Mid_Index]==Query_Element)
	return Mid_Index; //return Index of Query_Element
	if(data_array[Mid_Index] > Query_Element)
	Last_Index = Mid_Index -1;
	else
	First_Index = Mid_Index + 1;
	}
	//return -1 if not found Query_Element
	return -1;
	}

view raw Binary_Search.cpp hosted with ❤ by GitHub

Programming Puzzle

 

                One building has 100 floors. Egg will break if we throw it from Nth floor And Same egg will not break if we throw from (N-1)th floor. SO puzzle is to find out number of minimum throws to get N?

Write the answer in the comments and also explain your method.