Binary Search

Binary search is an efficient algorithm for finding an item from an ordered list of items. It works by repeatedly dividing in half the portion of the list that could contain the item until you've narrowed down the possible locations to just one.

One of the most common ways to use binary search is to find an item in an array. For example, the Tycho-2 star catalog contains information about the brightest 2,539,913 stars in our galaxy. Suppose that you want to search the catalog for a particular star, based on the star's name. If the program examined every star in the star catalog in order starting with the first, an algorithm called linear search, the computer might have to examine all 2,539,913 stars to find the star you were looking for, in the worst case. If the catalog were sorted alphabetically by star names, binary search would not have to examine more than 22 stars, even in the worst case.

https://www.youtube.com/watch?v=ao3iCcmTa10&list=PLCiOXwirraUB0HOYmEbmx-7KStKtoXZ6E&index=6

Procedure

Given below are the steps/procedures of the Binary Search algorithm.

• In each step, it compares the search key with the value of the middle element of the array.
• The keys matching in step 1 means, a matching element has been found and its index (or position) is returned. Else step 3 or 4.
• If the search key is less than the middle element, then the algorithm repeats its action on the sub-array to the left of the middle element or,
• If the search key is greater than the middle element, then the algorithm repeats its action on the sub-array to the right of the middle element.
• If the search key is not matching any of the subsequent left or right array, then it means that the key is not present in the array and a special "Nil" indication can be returned.

Pseudocode example

1. Let min = 1 and max = n. these are the positions not actual values
2. Calculate the middle (min + max)/2, rounded down so that it is an integer.
3. Check the value at the middle position. if it is what you want, stop.
4. If the middle value was too low, set min to be middle position + 1.
5. If the middle value was too high, set max to be middle position -1.
6. Go back to step two.

Programming example

public static object BinarySearchIterative(int[] inputArray, int key, int min, int max)
{
    while (min <=max)
    {
       int mid = (min + max) / 2;
       if (key == inputArray[mid])
       {
            return ++mid;
       }
       else if (key < inputArray[mid])
       {
           max = mid - 1;
       }
       else
       {
            min = mid + 1;
       }
   }
   return "Nil";
}