Binary search — intermediate problems

Integer square root by searching an answer range, minimum in a rotated sorted array, and a peak using only index comparisons.

Problem 1 — Integer square root

Task: Given n ≥ 0, find ⌊√n⌋ (largest r with r*r ≤ n).

Idea: The answer is in [0, n] and the predicate r*r ≤ n is false then true as r grows… actually we want the largest r with r*r ≤ n. Binary search mid: if mid*mid ≤ n, try larger — move lo = mid; else hi = mid - 1. Use long long for products.

Explanation: Monotone in r: if r works, any smaller non-negative r works too; we want the maximum feasible r.

Solution 1 — code

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long n;
    cin >> n;
    long long lo = 0, hi = n;
    while (lo < hi) {
        long long mid = lo + (hi - lo + 1) / 2;  // bias up so lo can move
        if (mid <= n / mid)  // mid*mid <= n without overflow
            lo = mid;
        else
            hi = mid - 1;
    }
    cout << lo << "\n";
    return 0;
}

Note: mid <= n / mid is a safe way to test mid*mid <= n for non-negative integers.

Problem 2 — Minimum in a rotated sorted array

Task: a was sorted ascending, then rotated unknown times. All values are distinct. Return the minimum.

Idea: Look at a[mid] and a[hi]. If a[mid] > a[hi], the drop (minimum) lies after mid, so lo = mid + 1. Otherwise the minimum is at mid or to the left — hi = mid.

Explanation: In the rotated picture, one half is always “sorted”; comparing with the right end tells which side contains the break.

Solution 2 — code

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> a = {6, 7, 1, 2, 3, 4, 5};
    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;
        else hi = mid;
    }
    cout << a[lo] << "\n";  // 1
    return 0;
}

Problem 3 — Find a peak index

Task: a has length ≥ 1 and some index is a peak: neighbors exist and a[i-1] < a[i] > a[i+1] (for boundaries, only compare existing neighbors). Return any peak index.

Idea: Pick mid. If a[mid] < a[mid+1], walk uphill to the right — lo = mid + 1. Else a peak is at mid or left — hi = mid. With one element, that index is a peak.

Explanation: Walking toward the larger neighbor cannot trap you in a valley; you eventually reach a local maximum.

Solution 3 — code

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> a = {1, 3, 5, 4, 2};
    int lo = 0, hi = (int)a.size() - 1;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] < a[mid + 1]) lo = mid + 1;
        else hi = mid;
    }
    cout << lo << "\n";  // index of a peak (e.g. 2)
    return 0;
}

Pattern summary

Problem 1 searches a numeric answer; Problems 2–3 compare mid with one boundary or neighbor to decide which half still has the answer.

1// Peak (0-based, lo..hi inclusive)
2while lo < hi
3  mid = lo + (hi - lo) / 2
4  if a[mid] < a[mid + 1] then lo = mid + 1
5  else hi = mid
6return lo

Complexity

Each problem uses O(log n) steps; Problem 1 uses O(1) work per step.

Complexity Analysis

Time Complexity

O(log n) for array problems; O(log n) for sqrt on value n

Space Complexity

O(1) extra

Growth Rate Comparison