Trace a Search for a Value That Is Not There

The bounds cross, and where low stops is where the value would go.

When the target is not in a sorted array, binary search ends with its two bounds crossed, and the index where low stops is where the target would have to be inserted to keep the array sorted. This walkthrough runs one such search comparison by comparison, shows the moment the bounds cross, and checks the stopping point against Python's own insertion-point function. You need it whenever a lookup can miss and the caller wants to know where the value belongs.

It uses the usual loop: low and high start at the first and last index, mid is halfway between them rounded down, low moves to mid + 1 when the middle item is too small, high moves to mid - 1 when it is too large, and the loop runs while low <= high.

Before the trace: a search looks for 30 in 4 9 15 21 28 37 44 52. At which index does low stop when the search gives up?

Index 5, where 37 sits: the first item larger than 30. The trace shows how low gets there.

The trace shows low, mid and high at every comparison, from an instrumented run. Watch the last frame, where the bounds cross.

Binary search for 30, which is not in the array

Input4 9 15 21 28 37 44 52, indices 0 to 7

Compare 30 with 21
1. 4low
2. 9
3. 15
4. 21mid
5. 28
6. 37
7. 44
8. 52high
21 is smaller than 30, so 30 can only be to the right of index 3: low moves to 4.
Compare 30 with 37
1. 4
2. 9
3. 15
4. 21
5. 28low
6. 37mid
7. 44
8. 52high
37 is larger than 30, so 30 can only be to the left of index 5: high moves to 4.
Compare 30 with 28
1. 4
2. 9
3. 15
4. 21
5. 28lowmidhigh
6. 37
7. 44
8. 52
28 is smaller than 30, so 30 can only be to the right of index 4: low moves to 5.
Bounds cross
1. 4
2. 9
3. 15
4. 21
5. 28high
6. 37low
7. 44
8. 52
low is past high, so no index is left to check: the search returns -1, and low stops at 5, where 30 would go.

ResultNot found; low stops at index 5, where 30 would be inserted

Step by step. The first two comparisons narrow the range as any search does: 21 is too small, so low moves to 4, and 37 is too large, so high moves to 4. The range is now the single index 4, and a one-item range still has to be checked, which is why the loop runs while low <= high and not while low < high. 28 is too small, so low moves to 5, one past high, and the loop stops with nothing left to check.

Why low lands on the gap. Every move of low stepped past items known to be smaller than 30, and every move of high stepped past items known to be larger. When they cross, everything left of low is smaller and everything from low onwards is larger, so low sits exactly at the boundary. Inserting 30 at index 5 gives 4 9 15 21 28 30 37 44 52, still sorted, and the same reasoning holds for any value that misses.

How you know it worked. The run printed search 30: -1, the usual signal for a value that is absent, and bisect_left 30: 5, Python's standard insertion point for 30 in the same array. The index where low stopped and the library's answer agree. A search that returns low on a miss, instead of -1, gives its caller both facts at once: that the value is missing, and where it belongs.

← → move through sections and cards