Binary Search

High-Low Game

High Low game is one where one person picks a number between a range (say 1-100) and another person have to guess it. With each guess, s/he is told whether the guess was high, low or correct.

If the person picking the number picks it at random, then the best strategy would be to use binary search algorithm (start at middle of range, and then keep dividing sample space in half) to minimize the number of guesses.

What is Binary Search

Binary search searches for an item in an array. Binary search has the same interface and return values as linear search. In binary search item in the array must be sorted. Binary search is significantly faster than linear search.

Binary search strategy

• Define a search area with a starting and ending index
• Halve the search at each steps
• A middle index is chosen so that the left and right sub-arrays have an equal number of elements (+/- 1)
• Values to the left of the middle are less than the middle
• Values to the right of the middle are greater than the middle value

Algorithm

1. Set start to 0
2. Set end to the last item (array count - 1)
3. While start is less than or equal to end:
   • Calculate the middle index
   • If value in middle is - Equal to target, return the index - less than target, set up boundaries for the left side - greater than target, set up boundaries for the right side
4. Raise an exception if target is not found

Pseudocode

1. Set start = 0
2. Set end = array count - 1
3. While start <= end
4. Set middle = integer of ((start + end) / 2)
5. if array[middle] = target, return middle
6. else if array[middle] > target, set end = middle - 1
7. else if array[middle] < target, set start = middle + 1
8. Raise exception

start = 0
end = len(array) - 1
while start <= end:
   middle = (start + end) // 2
   if array[middle] > target:
      end = middle - 1
   elif array[middle] < target:
      start = middle + 1

Complexity

Binary search vs Linear search

Topics

• Big O notation
• Linear Search
• Arrays