Core Concept Mastery • DSA Module
Binary search only works when the list is sorted. You look at the middle item. If it is the target, you are done. If the target is smaller, search the left half. If the target is larger, search the right half. Repeat. Each step cuts the search space in half, so worst case is O(log n).
If the list is Sorted, we can be smarter: cut it in half each time.
Look for the word "Magic". Open the book in the middle. You see "Lemon". "Magic" comes after "Lemon", so throw away the first half. Repeat with the second half.
Binary search only works on a sorted array.
Watch how we cut the problem in half every time.
Halving search space. O(log n).
1while (low <= high) {2int mid = low + (high - low) / 2;34if (arr[mid] == target)5return mid; // Found!67if (arr[mid] < target)8low = mid + 1; // Throw away left half9else10high = mid - 1; // Throw away right half11}
Steps depend linearly on input.
Input gets cut in half each time.
| Case | Time | Note |
|---|---|---|
| Best | O(1) | Middle item is the target. |
| Worst | O(log n) | Cut in half until one item left. |
For 1,000,000 items, binary search needs about 20 steps. Linear search can need 1,000,000.
The rule: sorted only
Binary search uses the order of the list. It compares the target with the middle item and then throws away one half. So the list must be sorted. If it is not sorted, the logic is wrong and you may say "not found" even when the value is there.
The dictionary trick
You look for the word "Magic". You open the book in the middle. You see "Lemon". "Magic" comes after "Lemon", so you throw away the first half. You repeat with the second half. Each time you cut the problem in half.
Time complexity
On a sorted list, binary search is much faster than linear search for large lists. For a million items, linear can take a million steps; binary takes about 20 steps.