Working out which half is trustworthy

When one half is reliably sorted and the other is not, you can still decide where to go.

Key idea

What a sorted half buys you

For a sorted half, deciding whether a target is inside it is a single range test: is the target at or above the left end and at or below the right end?

If it is, search that half. If it is not, the target can only be in the messy half, so search that one instead. Either way you discard half, and the messy half becomes the new problem, which has the same structure.

That is the whole algorithm: identify the trustworthy half, use it to make a decision, recurse on whichever half survives.

1def half_is_sorted(values, low, high):2    return values[low] <= values[high]3 4values = [4, 5, 6, 7, 0, 1, 2]5mid = 36 7print(half_is_sorted(values, 0, mid))       # left half 4,5,6,78print(half_is_sorted(values, mid, 6))       # right half 7,0,1,2

Find the bug· 5 min

Find the branch that will not shrink

This finds the smallest value in a rotated sorted array, which is the problem you just solved. It hangs on some inputs. Click the line responsible.

Click the line you think is wrong

Problem· 28 min

Search In Rotated Sorted Array

Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.

Binary Search

43 / 170

Binary SearchLesson 5 of 8About 44 min