3.11 Binary Search Summary Notes

Binary search is an algorithm that finds an element in a sorted list. It is much more efficient than Linear Search (3.10) because half of a list is eliminated every iteration that the value is not found.

Procedure

1. Start at the middle element of a list. If there are 2 middle elements, choose whichever one.
2. Compare the target value to that middle element.
   • If the value is greater, eliminate the middle element and everything to the left of it.
   • If less, eliminate the middle element and everything to the right.
   • If equal, the target value has been found in the list.
3. Repeat steps 1-2 until the target value is found, or only 1 value is left and it is not equal to the target value.

Pseudocode

PROCEDURE binarySearch(list, value)
{
  startIndex ← 1
  endIndex ← LENGTH(list)
  REPEAT UNTIL(endIndex < startIndex)
  {
    middleIndex ← startIndex + (endIndex - startIndex) / 2
    middleIndex ← middleIndex - middleIndex % 1
    IF(list[middleIndex] = value)
    {
      RETURN(middleIndex)
    }
    ELSE
    {
      IF(list[middleIndex] > value)
      {
        endIndex ← middleIndex - 1
      }
      ELSE
      {
        startIndex ← middleIndex + 1
      }
    }
  }
  RETURN(-1)
}

A challenge can be found in this Khan Academy link.