Binary Search

@binary_search

Binary Search is a very fast algorithm used to find a value in a sorted list by repeatedly cutting the search space in half until the item is found or nothing is left.

Pseudo-code
function binary_search(list, key):
  # Step 1: Define search boundaries
  low = 0
  high = length(list) - 1

  # Step 2: Keep searching while range is valid
  while low <= high:

    # Step 3: Find the middle index
    mid = (low + high) // 2

    # Step 4: Check if we found the key
    if list[mid] == key:
      return mid

    # Step 5: If key is bigger, ignore left half
    else if list[mid] < key:
      low = mid + 1

    # Step 6: If key is smaller, ignore right half
    else:
      high = mid - 1

  # Step 7: If not found
  return -1
  • list Sorted array you are searching in. It must already be in order.
  • low Starting index of the current search range (left boundary).
  • high Ending index of the current search range (right boundary).
  • key Value you are trying to find.
  • mid Middle position between low and high. This is where we check first.
  • 0 First index of the list.
  • length-1 Last index of the list.
Recipe Steps
1

Start in the middle — Imagine searching in a dictionary. You open it in the middle first.

2

Compare your target with the middle item. Ask: Is my value bigger or smaller?

3

Throw away half — If your value is bigger, ignore the left half. If smaller, ignore the right half.

4

Repeat the same process on the remaining half.

5

Keep cutting in half until you find the value or nothing is left.

Questions & Answers

Because we rely on order to decide which half to ignore.

We cut the search space in half, making it very fast.

-1 (or some indication that the item does not exist).

mid = index 2 → value 5, so we search the right half next.
- Time complexity is O(log n), which is extremely fast.
- Each step removes half of the remaining elements.
- Tip: Always calculate mid using integer division (//).
- Common mistake: Using Binary Search on an unsorted list.
- Be careful with index boundaries to avoid infinite loops.

Related Algorithms
Boyer–Moore string-search algorithm

The Boyer–Moore string-search algorithm is a fast string searching algorithm that is often used in text editors and compilers. It does this by trying to match the pattern from the end of the string, making it efficient for large strings. It's used when you need to find a substring within a large text or string.

View
Counting Sort

Counting Sort is a sorting algorithm that does not compare elements. Instead, it counts how many times each number appears and uses that information to place elements directly in their correct position.

View
HeapSort

HeapSort is a sorting algorithm that uses a special tree structure called a heap. It repeatedly takes the largest element and moves it to the end, shrinking the unsorted part step by step until everything is sorted.

View