Binary search on a sorted range

When to use it

Use it when the list you search is given to you already in order, and one look at a position tells you on which side the answer lies.

It belongs to the search & scan group: Move one or two positions across the input so that nothing is looked at more than a few times.

Watch it work

A library shelf holds books in order of their numbers, and no number is used twice. A book with the number book comes back. Return the position where it goes so that the shelf stays in order, counting from 0.

Input
shelf = [12, 18, 23, 31, 40, 47, 55]
book = 35

Output
4

The method

1. The place is somewhere from position 0 to the end of the shelf
2. Look at the book in the middle of the range
3. Its number is smaller: the place is after it
4. Its number is larger: the place is here or before it
5. One position remains: that is the place

The run, one moment at a time

1. Step 1. Book 35 can go at any position from 0 to 7. Position 7 is the end, after the last book.

   shelf: 12 18 23 31 40 47 55 end  (left at 0, right at 7)
   book: 35
   

2. Step 2. The middle of positions 0 to 7 is position 3. The book there is 31.

   shelf: 12 18 23 31 40 47 55 end  (left at 0, mid at 3, right at 7)
   book: 35
   

3. Step 3. 31 is smaller than 35, so the place is after it. Positions 0 to 3 are ruled out: left moves to 4.

   shelf: 12 18 23 31 40 47 55 end  (left at 4, right at 7)
   book: 35
   

4. Step 2. The middle of positions 4 to 7 is position 5. The book there is 47.

   shelf: 12 18 23 31 40 47 55 end  (left at 4, mid at 5, right at 7)
   book: 35
   

5. Step 4. 47 is larger than 35, so the place is here or before it. Positions 6 and 7 are ruled out: right moves to 5.

   shelf: 12 18 23 31 40 47 55 end  (left at 4, right at 5)
   book: 35
   

6. Step 2. Two positions remain, 4 and 5. Their middle rounds down to 4, so mid and left are both there. The book is 40.

   shelf: 12 18 23 31 40 47 55 end  (both at 4, right at 5)
   book: 35
   

7. Step 4. 40 is larger than 35, so the place is here or before it. Position 5 is ruled out: right moves to 4.

   shelf: 12 18 23 31 40 47 55 end  (both at 4)
   book: 35
   

8. Step 5. Left and right are both 4, so one position remains. Book 35 goes at position 4, before 40.

   shelf: 12 18 23 31 40 47 55 end  (both at 4)
   book: 35
   

The code

The numbered comments are the steps of the method.

function solve(shelf, book) {
  // 1. The place is somewhere from position 0 to the end of the shelf
  let left = 0;
  let right = shelf.length;
  while (left < right) {
    // 2. Look at the book in the middle of the range
    const mid = Math.floor((left + right) / 2);
    if (shelf[mid] < book) {
      // 3. Its number is smaller: the place is after it
      left = mid + 1;
    } else {
      // 4. Its number is larger: the place is here or before it
      right = mid;
    }
  }
  // 5. One position remains: that is the place
  return left;
}

def solve(shelf, book):
    # 1. The place is somewhere from position 0 to the end of the shelf
    left = 0
    right = len(shelf)
    while left < right:
        # 2. Look at the book in the middle of the range
        mid = (left + right) // 2
        if shelf[mid] < book:
            # 3. Its number is smaller: the place is after it
            left = mid + 1
        else:
            # 4. Its number is larger: the place is here or before it
            right = mid
    # 5. One position remains: that is the place
    return left

How to spot it

Given: A list sorted from smallest to largest, and one value to find

Order lets one comparison rule out a whole side. Without order, every value has to be looked at.

Given: A sorted list was rotated: its first values moved to the end

It is still two sorted pieces. Comparing the middle with an end value tells which piece it is in, so half still goes.

Asked: The position of a value, or where it would go

In sorted data the smaller values come first. Halving finds where they stop, and that is the place of the value.

Limits: Aim for O(log n) time

Only halving is that fast. A list of 1,000,000 values is down to one position after about 20 looks.

Looks like it, but is not

• No list is given to search. You want the smallest speed, size or time that passes a check. Use Binary search on the answer. The halving is the same, but over a range of possible answers. A test there is a calculation over the input, not one look.
• The list is sorted and you need two values that add up to a target. Use Opposing two pointers. The answer is a pair, not one position. Start at both ends and move one end inward after each sum.
• The list is in no order and you must say whether a value is in it. Use Hash set membership. Halving needs order. Without it, put the values in a set, and each check is one step.

Cost and mistakes

Each look drops half of the range, so 1,000 books need about 10 looks and 1,000,000 need about 20. That is written O(log n). Extra space is three numbers, written O(1).

Watch out

• Move past the middle when you drop it: left = mid + 1. With left = mid, a range of two positions never shrinks, because the middle rounds down to left, and the loop never ends.
• There are two loop styles. Do not mix them. The loop left < right goes with right = mid. The loop left <= right goes with right = mid - 1.

In the 150

5 problems of the 150 use it. Naming them gives their method away, so the list is folded.