Search as the name suggests, is an operation of finding an item from the given collection of items. Binary Search algorithm is used to find the position of a specified value (an ‘Input Key’) given by the user in a sorted list.
It starts with the middle element of the list.
1. If the middle element of the list is equal to the ‘input key’ then we have found the position the specified value.
2. Else if the ‘input key’ is greater than the middle element then the ‘input key’ has to be present in the last half of the list.
3. Or if the ‘input key’ is lesser than the middle element then the ‘input key’ has to be present in the first half of the list.
Hence, the search list gets reduced by half after each iteration.
First, the list has to be sorted in non-decreasing order.
[low, high] denotes the range in which element has to be present and [mid] denotes the middle element. Initially low = 0, high = number_of_elements and mid = floor((low+high)/2). In every iteration we reduce the range by doing the following until low is less than or equal to high(meaning elements are left in the array) or the position of the ‘input key’ has been found.
(i) If the middle element (mid) is less than key then key has to present in range [mid+1 , high], so low=mid+1, high remains unchanged and mid is adjusted accordingly
(ii) If middle element is the key, then we are done.
(iii) If the middle element is greater than key then key has to be present in the range [low,mid-1], so high=mid-1, low remains unchanged and mid is adjusted accordingly.
1. Best Case performance – The middle element is equal to the ‘input key’ O(1).
2. Worst Case performance - The ‘input key’ is not present in the list O(logn).
3. Average Case performance – The ‘input key’ is present, but it’s not the middle element
4. The List should be sorted for using Binary Search Algorithm.
5. It is faster than Linear Search algorithm, and its performance increases in comaparison to
linear search as N grows.
Related Tutorials :
Recommended books for learning Computer Science, learning high quality programming, and preparing for programming interviews:
These are the standard sources of the knowledge expected from candidates interviewing at Google, Microsoft, Facebook, Amazon and other startups and top-tier technology companies. The books by Cormen or Sedgewick (a standard part of the undergraduate curriculum) are sufficient for this part of the preparation. Google specially, loves to focus on algorithmic questions.