Searching Exercises: Answer Sheet & Worked Solutions
This is the answer sheet for the searching exercises. Each solution gives the key idea, the optimal complexity, the code in all four languages (use the switcher), and common pitfalls. Try the problems first — then check your work here.
Q1. Binary search
Idea: Track an inclusive range [lo, hi]. Test the midpoint; if it’s too small move lo right, if too big move hi left. Each step halves the range. Use lo + (hi - lo) / 2 so the midpoint can’t overflow.
Complexity: O(log n) time, O(1) space.
int binarySearch(const std::vector<int>& a, int target) {
int lo = 0, hi = (int)a.size() - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (a[mid] == target) return mid;
else if (a[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
return -1;
}int binarySearch(int[] a, int target) {
int lo = 0, hi = a.length - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (a[mid] == target) return mid;
else if (a[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
return -1;
}function binarySearch(a, target) {
let lo = 0, hi = a.length - 1;
while (lo <= hi) {
const mid = lo + Math.floor((hi - lo) / 2);
if (a[mid] === target) return mid;
else if (a[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
return -1;
}def binary_search(a, target):
lo, hi = 0, len(a) - 1
while lo <= hi:
mid = lo + (hi - lo) // 2
if a[mid] == target:
return mid
elif a[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1Pitfall: With an inclusive range you must use
lo <= hiand move bounds tomid ± 1. Usinglo < himisses a final single-element range; settinghi = mid(notmid - 1) can loop forever.
Q2. Search insert position
Idea: This is exactly lower_bound: the first index whose element is >= target. Use the half-open [lo, hi) template and return lo — which equals the insertion point even when target is absent.
Complexity: O(log n) time, O(1) space.
int searchInsert(const std::vector<int>& a, int target) {
int lo = 0, hi = (int)a.size(); // half-open [lo, hi)
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (a[mid] < target) lo = mid + 1;
else hi = mid;
}
return lo;
}int searchInsert(int[] a, int target) {
int lo = 0, hi = a.length; // half-open [lo, hi)
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (a[mid] < target) lo = mid + 1;
else hi = mid;
}
return lo;
}function searchInsert(a, target) {
let lo = 0, hi = a.length; // half-open [lo, hi)
while (lo < hi) {
const mid = lo + Math.floor((hi - lo) / 2);
if (a[mid] < target) lo = mid + 1;
else hi = mid;
}
return lo;
}def search_insert(a, target):
lo, hi = 0, len(a) # half-open [lo, hi)
while lo < hi:
mid = lo + (hi - lo) // 2
if a[mid] < target:
lo = mid + 1
else:
hi = mid
return loPitfall: Initialize
hi = n(one past the end), notn - 1. Iftargetis larger than every element, the answer isn, and that’s only reachable whenhican reachn.
Q3. Count occurrences of a value
Idea: Count = upperBound(target) - lowerBound(target). lowerBound is the first index >= target; upperBound is the first index > target. Their gap is exactly how many equal target. No need to find each copy.
Complexity: O(log n) time, O(1) space.
int lowerBound(const std::vector<int>& a, int t) {
int lo = 0, hi = (int)a.size();
while (lo < hi) { int m = lo + (hi - lo) / 2; if (a[m] < t) lo = m + 1; else hi = m; }
return lo;
}
int upperBound(const std::vector<int>& a, int t) {
int lo = 0, hi = (int)a.size();
while (lo < hi) { int m = lo + (hi - lo) / 2; if (a[m] <= t) lo = m + 1; else hi = m; }
return lo;
}
int countOccurrences(const std::vector<int>& a, int target) {
return upperBound(a, target) - lowerBound(a, target);
}int lowerBound(int[] a, int t) {
int lo = 0, hi = a.length;
while (lo < hi) { int m = lo + (hi - lo) / 2; if (a[m] < t) lo = m + 1; else hi = m; }
return lo;
}
int upperBound(int[] a, int t) {
int lo = 0, hi = a.length;
while (lo < hi) { int m = lo + (hi - lo) / 2; if (a[m] <= t) lo = m + 1; else hi = m; }
return lo;
}
int countOccurrences(int[] a, int target) {
return upperBound(a, target) - lowerBound(a, target);
}function lowerBound(a, t) {
let lo = 0, hi = a.length;
while (lo < hi) { const m = lo + Math.floor((hi - lo) / 2); if (a[m] < t) lo = m + 1; else hi = m; }
return lo;
}
function upperBound(a, t) {
let lo = 0, hi = a.length;
while (lo < hi) { const m = lo + Math.floor((hi - lo) / 2); if (a[m] <= t) lo = m + 1; else hi = m; }
return lo;
}
function countOccurrences(a, target) {
return upperBound(a, target) - lowerBound(a, target);
}def lower_bound(a, t):
lo, hi = 0, len(a)
while lo < hi:
m = lo + (hi - lo) // 2
if a[m] < t: lo = m + 1
else: hi = m
return lo
def upper_bound(a, t):
lo, hi = 0, len(a)
while lo < hi:
m = lo + (hi - lo) // 2
if a[m] <= t: lo = m + 1
else: hi = m
return lo
def count_occurrences(a, target):
return upper_bound(a, target) - lower_bound(a, target)Pitfall: The only difference between the two bounds is
<vs<=. Swap them by accident and you’ll get a count of 0 or a negative number. (Python’sbisect.bisect_right - bisect.bisect_leftdoes the same thing.)
Q4. Two Sum II (sorted input)
Idea: Two pointers from opposite ends. If the pair sum is too small, move lo right for a larger value; if too big, move hi left. Each step provably discards one candidate, so it’s a single linear sweep — no extra memory, unlike the hash-map version for unsorted input.
Complexity: O(n) time, O(1) space.
std::pair<int,int> twoSumSorted(const std::vector<int>& a, int target) {
int lo = 0, hi = (int)a.size() - 1;
while (lo < hi) {
int s = a[lo] + a[hi];
if (s == target) return {lo, hi};
else if (s < target) lo++;
else hi--;
}
return {-1, -1};
}int[] twoSumSorted(int[] a, int target) {
int lo = 0, hi = a.length - 1;
while (lo < hi) {
int s = a[lo] + a[hi];
if (s == target) return new int[]{lo, hi};
else if (s < target) lo++;
else hi--;
}
return new int[]{-1, -1};
}function twoSumSorted(a, target) {
let lo = 0, hi = a.length - 1;
while (lo < hi) {
const s = a[lo] + a[hi];
if (s === target) return [lo, hi];
else if (s < target) lo++;
else hi--;
}
return [-1, -1];
}def two_sum_sorted(a, target):
lo, hi = 0, len(a) - 1
while lo < hi:
s = a[lo] + a[hi]
if s == target:
return (lo, hi)
elif s < target:
lo += 1
else:
hi -= 1
return (-1, -1)Pitfall: Two pointers only works because the array is sorted. On unsorted input you can’t tell which pointer to move — use a hash map instead.
Q5. Integer square root
Idea: Binary-search the answer in [0, n] for the largest k with k*k <= n. Keep the best feasible k as you go. Compare with 64-bit math so mid*mid doesn’t overflow.
Complexity: O(log n) time, O(1) space.
int isqrt(int n) {
long long lo = 0, hi = n, ans = 0;
while (lo <= hi) {
long long mid = lo + (hi - lo) / 2;
if (mid * mid <= (long long)n) { ans = mid; lo = mid + 1; }
else hi = mid - 1;
}
return (int)ans;
}int isqrt(int n) {
long lo = 0, hi = n, ans = 0;
while (lo <= hi) {
long mid = lo + (hi - lo) / 2;
if (mid * mid <= (long) n) { ans = mid; lo = mid + 1; }
else hi = mid - 1;
}
return (int) ans;
}function isqrt(n) {
let lo = 0, hi = n, ans = 0;
while (lo <= hi) {
const mid = lo + Math.floor((hi - lo) / 2);
if (mid * mid <= n) { ans = mid; lo = mid + 1; }
else hi = mid - 1;
}
return ans;
}def isqrt(n):
lo, hi, ans = 0, n, 0
while lo <= hi:
mid = lo + (hi - lo) // 2
if mid * mid <= n:
ans = mid
lo = mid + 1
else:
hi = mid - 1
return ansPitfall: In C++/Java,
mid * midoverflows 32-bitintfor largen. Do the multiply inlong/long long(as above). JavaScript and Python integers don’t have this issue.
Q6. Find minimum in a rotated sorted array
Idea: Binary search comparing a[mid] to the right end a[hi]. If a[mid] > a[hi], the rotation point (and hence the minimum) is to the right of mid, so lo = mid + 1. Otherwise the minimum is at mid or left, so hi = mid. The range collapses onto the minimum.
Complexity: O(log n) time, O(1) space.
int findMin(const std::vector<int>& a) {
int lo = 0, hi = (int)a.size() - 1;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (a[mid] > a[hi]) lo = mid + 1; // min is to the right
else hi = mid; // min is mid or to the left
}
return a[lo];
}int findMin(int[] a) {
int lo = 0, hi = a.length - 1;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (a[mid] > a[hi]) lo = mid + 1; // min is to the right
else hi = mid; // min is mid or to the left
}
return a[lo];
}function findMin(a) {
let lo = 0, hi = a.length - 1;
while (lo < hi) {
const mid = lo + Math.floor((hi - lo) / 2);
if (a[mid] > a[hi]) lo = mid + 1; // min is to the right
else hi = mid; // min is mid or to the left
}
return a[lo];
}def find_min(a):
lo, hi = 0, len(a) - 1
while lo < hi:
mid = lo + (hi - lo) // 2
if a[mid] > a[hi]:
lo = mid + 1 # min is to the right
else:
hi = mid # min is mid or to the left
return a[lo]Pitfall: Compare to
a[hi], nota[lo]. Comparing to the left end is ambiguous when the array isn’t rotated. Also note this assumes distinct values — duplicates (e.g.[3,3,1,3]) break the strict comparison and need an extrahi--fallback.
Q7. Capacity to ship packages within D days
Idea: Binary search on the answer. Capacity must be at least the heaviest package (max) and at most all packages in one day (sum). feasible(cap) greedily counts days: keep loading until the next package would overflow cap, then start a new day. Search the smallest cap whose day count is <= days — feasibility is monotonic in cap.
Complexity: O(n · log(sum)) time, O(1) space.
int daysNeeded(const std::vector<int>& w, int cap) {
int days = 1, cur = 0;
for (int x : w) {
if (cur + x > cap) { days++; cur = 0; }
cur += x;
}
return days;
}
int shipWithinDays(const std::vector<int>& w, int days) {
int lo = 0, hi = 0;
for (int x : w) { lo = std::max(lo, x); hi += x; } // [max, sum]
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (daysNeeded(w, mid) <= days) hi = mid; // feasible, try smaller
else lo = mid + 1; // too small, grow
}
return lo;
}int daysNeeded(int[] w, int cap) {
int days = 1, cur = 0;
for (int x : w) {
if (cur + x > cap) { days++; cur = 0; }
cur += x;
}
return days;
}
int shipWithinDays(int[] w, int days) {
int lo = 0, hi = 0;
for (int x : w) { lo = Math.max(lo, x); hi += x; } // [max, sum]
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (daysNeeded(w, mid) <= days) hi = mid; // feasible, try smaller
else lo = mid + 1; // too small, grow
}
return lo;
}function daysNeeded(w, cap) {
let days = 1, cur = 0;
for (const x of w) {
if (cur + x > cap) { days++; cur = 0; }
cur += x;
}
return days;
}
function shipWithinDays(w, days) {
let lo = Math.max(...w);
let hi = w.reduce((s, x) => s + x, 0); // [max, sum]
while (lo < hi) {
const mid = lo + Math.floor((hi - lo) / 2);
if (daysNeeded(w, mid) <= days) hi = mid; // feasible, try smaller
else lo = mid + 1; // too small, grow
}
return lo;
}def days_needed(w, cap):
days, cur = 1, 0
for x in w:
if cur + x > cap:
days += 1
cur = 0
cur += x
return days
def ship_within_days(w, days):
lo, hi = max(w), sum(w) # [max, sum]
while lo < hi:
mid = lo + (hi - lo) // 2
if days_needed(w, mid) <= days:
hi = mid # feasible, try smaller
else:
lo = mid + 1 # too small, grow
return loPitfall: The lower bound must be
max(weights), not1— a capacity below the heaviest package can never ship it, and your greedy check would loop forever or undercount. Always set the answer range to genuinely possible values.
That’s the full answer sheet. Back to the searching exercises or continue to sliding window.