The example problem
Given a list of numbers sorted from small to large and a target number, return the position of the target, or −1 if it is not in the list.
Input: [3,7,12,18,23,29,34,38,42,47,51,56,63,70,77], target = 42 Output: 8 (positions count from 0)
Picture it
Picture a long library shelf where books are arranged by number. Instead of checking books one by one, pull out the middle book. If its number is too small, the book you want must be in the right half, so you can ignore the whole left half. Too big? Ignore the right half. Each look throws away half the shelf, so even 1,000 books need only about 10 looks.
The key idea
Keep a range [lo, hi] that must contain the answer and halve it every step: O(log n).
Python
def search(books, target):
lo, hi = 0, len(books) - 1
while lo <= hi:
mid = (lo + hi) // 2
if books[mid] == target:
return mid
if books[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1Practise binary search
- LeetCode 34Find First and Last Position of Element in Sorted ArrayAll copies of one book on a sorted shelf
- LeetCode 35Search Insert PositionWhere does the new book go?
- LeetCode 162Find Peak ElementA hiker who always walks uphill
- LeetCode 540Single Element in a Sorted ArrayThe lone sock on a line of pairs
- LeetCode 1351Count Negative Numbers in a Sorted MatrixA staircase walk through freezing readings
- LeetCode 4Median of Two Sorted ArraysCutting two sorted shelves in half together
NeetCode 150 problems that use it
Binary Search ·
- LeetCode 704 · EasyBinary SearchFinding a book on a sorted shelf
- LeetCode 74 · MediumSearch a 2D MatrixAn elevator that searches a sorted apartment block
- LeetCode 875 · MediumKoko Eating BananasFinding the slowest eating speed that still works
- LeetCode 153 · MediumFind Minimum in Rotated Sorted ArrayA clock face someone turned
- LeetCode 33 · MediumSearch in Rotated Sorted ArrayFinding a number on a turned clock face
- LeetCode 981 · MediumTime Based Key-Value StoreA diary that answers “what was it at time t?”
- LeetCode 4 · HardMedian of Two Sorted ArraysCutting two sorted shelves in half together