Binary Search
From classic sorted array search to binary search on the answer — master the O(log n) elimination technique.
Questions in this quiz
10 questions on Binary Search. Work through them here, then start the quiz to answer them and see your score.
1.What is the primary prerequisite for binary search to work correctly?
- AThe array must contain only positive integers
- BThe array length must be a power of 2
- CThe search space must be sorted or have a monotonic property
- DNo duplicate elements allowed
2.What is the time complexity of binary search?
- AO(1)
- BO(n log n)
- CO(log n)
- DO(n)
3.Why write `mid = lo + (hi - lo) / 2` instead of `mid = (lo + hi) / 2`?
- AGives a different result for even-length arrays
- BAvoids integer overflow when lo and hi are both close to Integer.MAX_VALUE
- CRequired by the Java compiler
- DFaster arithmetic
4.What does this code return for nums = [1,3,5,6], target = 5?
public int searchInsert(int[] nums, int target) { int lo = 0, hi = nums.length; while (lo < hi) { int mid = lo + (hi - lo) / 2; if (nums[mid] < target) lo = mid + 1; else hi = mid; } return lo; }- A3
- B0
- C1
- D2
5.When searching for the leftmost (first) occurrence of a target, what do you do when target is found at mid?
- AReturn mid immediately — standard binary search
- BUse linear scan to the left after finding any occurrence
- CRecord mid as a candidate, then continue searching right (lo = mid + 1)
- DRecord mid as a candidate, then continue searching left (hi = mid - 1)
6.What does "binary search on the answer" mean?
- AUsing recursion instead of iteration
- BSearching an answer key for correct responses
- CBinary searching over a range of possible answer values, checking feasibility at each midpoint
- DA dynamic programming optimization technique
7.You have a rotated sorted array [4,5,6,7,0,1,2]. Can binary search efficiently find a target?
- ANo — you must un-rotate the array first
- BYes — at each step one half is always fully sorted; check if target is in the sorted half
- CYes — but only if the target is in the left half
- DNo — the array is not sorted, so binary search is invalid
8.What does this return for nums = [-1, 0, 3, 5, 9, 12], target = 9?
public int search(int[] nums, int target) { int lo = 0, hi = nums.length - 1; while (lo <= hi) { int mid = lo + (hi - lo) / 2; if (nums[mid] == target) return mid; if (nums[mid] < target) lo = mid + 1; else hi = mid - 1; } return -1; }- A4
- B3
- C5
- D-1
9.Find Peak Element: a peak is an element greater than its neighbours. Can binary search work here even though the array is not sorted?
- AYes — but only if the array is unimodal
- BYes — if nums[mid] < nums[mid+1], a peak must exist in the right half; otherwise it exists in the left half
- CNo — use a stack instead
- DNo — linear scan O(n) is required
10.What is the space complexity of iterative binary search vs recursive binary search?
- ABoth O(log n)
- BIterative: O(log n), Recursive: O(1)
- CBoth O(1)
- DIterative: O(1), Recursive: O(log n) due to call stack frames