Algorithms: Searching and Simple Sorting

1. When The items are sorted, and you need where a value belongs or how many items equal it

   , choose

   Lower Bound, Upper Bound

2. When The items are sorted, and you look one value up, perhaps many times

   , choose

   Binary Search

3. When There are only a few items, or the input is already nearly sorted

   , choose

   Insertion Sort

4. When Writing an item costs far more than comparing two

   , choose

   Selection Sort

5. When You need one pass that also confirms the input is already sorted

   , choose

   Bubble Sort

Both halve a sorted range: one finds a value, and the other finds where a value belongs.

• Binary Search

  Compare with the middle of a sorted range, then discard the half that cannot hold the target.

  Use when

  The items are sorted, and you look one value up, perhaps many times.

  Facts

  Find

  O(log n)

  worst case, the range halves at each step

  Find

  O(1)

  best case, the target is the first midpoint

  Extra space

  O(1)

  every case, two indices and a midpoint

  Snippet

  def binary_search(items, target):
      low, high = 0, len(items) - 1
      while low <= high:
          mid = low + (high - low) // 2
          if items[mid] == target: return mid
          if items[mid] < target: low = mid + 1
          else: high = mid - 1
      return -1

• Lower Bound, Upper Bound

  Binary search over [low, high) that returns where a value belongs, not only whether it is there.

  Use when

  The items are sorted, and you need where a value belongs or how many items equal it.

  Facts

  Lower bound

  O(log n)

  worst case, the first index whose item is at least the target

  Upper bound

  O(log n)

  worst case, the first index whose item is greater than the target

  Count of the target

  O(log n)

  worst case, upper bound minus lower bound

  Snippet

  def lower_bound(items, target):
      low, high = 0, len(items)
      while low < high:
          mid = low + (high - low) // 2
          if items[mid] < target: low = mid + 1
          else: high = mid
      return low

Each grows a sorted part one item at a time, and they differ in where the next item comes from.

• Insertion Sort

  Take the next item and shift larger sorted items right until its place opens.

  Use when

  Few items, or input that is already nearly sorted, or items arriving one at a time.

  Facts

  Time

  O(n)

  best case, the input already sorted

  Time

  O(n²)

  average and worst case, reversed input is the worst

  Stable

  yes

  in every case, equal items never pass each other

  Snippet

  def insertion_sort(items):
      for i in range(1, len(items)):
          current = items[i]
          j = i - 1
          while j >= 0 and items[j] > current:
              items[j + 1] = items[j]
              j -= 1
          items[j + 1] = current

• Selection Sort

  Find the smallest of what remains, then swap it to the front of the unsorted part.

  Use when

  Writing an item costs far more than comparing two, so the fewest swaps wins.

  Facts

  Comparisons

  n(n − 1)/2

  every case, so O(n²) even on sorted input

  Swaps

  n − 1

  worst case, at most one per position

  Stable

  no

  in general, a long swap can carry an item past its equal

  Snippet

  def selection_sort(items):
      for i in range(len(items) - 1):
          least = i
          for j in range(i + 1, len(items)):
              if items[j] < items[least]:
                  least = j
          items[i], items[least] = items[least], items[i]

• Bubble Sort

  Swap neighbours that are out of order; each pass carries the largest remaining item to the end.

  Use when

  Teaching, or one pass that also confirms the input is already sorted.

  Facts

  Time

  O(n)

  best case, sorted input with the early exit

  Time

  O(n²)

  average and worst case, reversed input is the worst

  Stable

  yes

  in every case, only unequal neighbours swap

  Snippet

  for end in range(len(items) - 1, 0, -1):
      swapped = False
      for j in range(end):
          if items[j] > items[j + 1]:
              items[j], items[j + 1] = items[j + 1], items[j]
              swapped = True
      if not swapped:
          break

1. 01

   Computing the midpoint as (low + high) / 2 in Java, which overflows past about a billion.

   A Midpoint That Overflows

2. 02

   Reading a negative result from Java's binarySearch as only not found, when it encodes the insertion point.

   Reading a Negative Result From Java's binarySearch as Only Not Found

3. 03

   Expecting an O(n) best case from a bubble sort that never checks for a pass without swaps.

   Expecting an O(n) Best Case From a Bubble Sort Without the Early Exit

• Binary Search5 questions

  Practise

• Elementary Sorting5 questions

  Practise