Overview

Modified Binary Search is a search algorithm that finds the left-most or right-most occurrence of a target within a range.

There are three main types of binary search:

• List-Based Binary Search: The most common type of binary search. You're asked to find the left/right-most occurrence of something within a (usually sorted) list.
• Range-Based Binary Search: Likely the least common type of binary search. You're given a range of numbers to search in (e.g. -10 to 100). You'll usually need to write a validation function.
• Tree-Based Binary Search: Tree-based binary search relies on the binary search tree to find a target, using tree traversal. Usually you won't be asked to implement this type of binary search since it's more of a data structure than an algorithm.

We'll be focusing on list-based binary search and range-based binary search for this pattern.

Pattern concept

Step 1 of 30

Use ← → arrow keys

Solution templates

List-Based Binary Search

Range-Based Binary Search

Implementing binary search can be tricky since there are many edge cases to account for. The templates above are created to be simple to reason through.

There are 4 main steps in solving a binary search problem:

• Variable Initialization

  You always need the following variables:

  • lo: The left-most index of the range.
  • hi: The right-most index of the range.

    Note

    We use inclusive array indexing, so that the values that lo and hi point to are included in the search.

  • arr: The array that we are searching. Usually this is given to you, but sometimes you need to create it or sort it yourself.
  • result: The result of the search. This can be set to None or -1 in the beginning. If it's still the same value at the end of the search, then the target was not found.

• Binary Search Initialization

  Only continue searching if lo has not passed hi yet. (In other words, keep searching if lo <= hi!)

  Start a new search by finding the midpoint of the list. There are two ways to find the midpoint that are mathematically equivalent; pick your favorite:

  mid = (hi - lo) // 2 + lo

  or

  mid = (hi + lo) // 2

• Validation

  Check if we found the target. If we did, great! Most of the time we want to break out of the loop early.

  However, if we need the left-most or right-most occurrence of the target, then we have to continue searching.

• Search

  Decide which half of the list to continue searching. Update lo or hi based on the side you pick.

  Because we are using inclusive indexing, always skip over the index that we validated on!

  Example: lo = mid + 1 or hi = mid - 1.

  Note

  This is the hardest part of the binary search! Take your time thinking about it.

How to identify

Does the problem involve any of these?

• Searching for the left-most (earliest/first/minimum) occurrence of a target within a range
  • First Bad Version: Search for the earliest/left-most bad version.
  • Search in Rotated Sorted List: Search for the first/left-most target when half the list is sorted.
  • Capacity to Transfer Packages: Search for the minimum/left-most capacity of baskets that can carry all packages.
• Searching for the right-most (latest/last/maximum) occurrence of a target within a range
  • First and Last Positions in a Sorted List: Search for the first/left-most and last/right-most positions of a target.
  • Maximum Count of Positives or Negatives: Search for the last/right-most negative integer and first/left-most positive integer.

By dividing the search range in half and searching only one half over and over again, we effectively do half the work at each stage. So if the size of the list doubles, the number of extra searches we need to do is only increased by one.

In other words, we need to divide and search the list O(log₂n) times to find our answer. In computer science, O(log₂n) can be written as O(logn).