Binary Search

Binary search is an efficient O(log n) way to search for a specific item in a list of sorted data, e.g. a list of integers [1, 2, 5, 8, 10, 18, 32, 60].

Steps

Given: sorted list, target value, start index, end index.

Initial case: start = 0, end = list.size

1. Calculate the midpoint index. mid = (start + end) / 2
2. Select the midpoint element of the sorted list. midpoint = list[mid]
3. Compare the midpoint element to the target value.
   1. If target = midpoint, then the value has been found. Return mid, which is the index of the target value.
   2. If target < midpoint, make a recursive call to search the lower half of the list. binarySearch(list, target, start, mid)
   3. If target > midpoint, make a recursive call to search the upper half of the list. binarySearch(list, target, mid + 1, end)

Image

External Links

• Wikipedia: Binary search algorithm
• GeeksForGeeks: Binary Search