Searching

Solution and explanation

Searching

Searching means finding whether (and where) a target value exists in a collection.

• Linear search checks elements one by one: works on any array, O(n).
• Binary search repeatedly halves a sorted range: O(log n).
• Hashing (HashMap/HashSet) finds keys in O(1) average time.

Binary search intuition

Looking up a word in a dictionary, you open the middle; if your word comes earlier, you discard the second half, and so on. Each step halves the search space, so 1,000,000 elements need at most about 20 comparisons (2^20 ≈ 10^6).

sorted: [2, 5, 8, 12, 16, 23, 38, 56, 72, 91], target 23
low=0, high=9 → mid=4 (16) < 23 → low=5
low=5, high=9 → mid=7 (56) > 23 → high=6
low=5, high=6 → mid=5 (23) found at index 5

static int binarySearch(int[] a, int target) {
    int low = 0, high = a.length - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;   // avoids int overflow of (low + high)
        if (a[mid] == target) return mid;
        if (a[mid] < target) low = mid + 1; else high = mid - 1;
    }
    return -1;
}

Requirements and pitfalls

• The data must be sorted (or the condition must be monotonic).
• Use mid = low + (high − low) / 2 to avoid overflow.
• Decide carefully between low <= high and low < high and how you move the bounds, or you will loop forever.

Binary search on the answer

Many problems are not about arrays at all: find the smallest capacity, speed or value x for which a yes/no check becomes true (e.g. "minimum days to ship packages"). If the check is monotonic, binary search over the range of possible answers.

Complexity

• Linear search: O(n) time, O(1) space.
• Binary search: O(log n) time, O(1) space iterative (O(log n) recursive).

Solution and explanation

Problem

Find the index of a target in an array (sorted or not); return −1 if absent.

Algorithm

Check each element from left to right.

static int linearSearch(int[] a, int target) {
    for (int i = 0; i < a.length; i++) {
        if (a[i] == target) return i;
    }
    return -1;
}

a = [10, 50, 30, 70, 80], target 30 → index 2
target 25 → -1

Sentinel optimisation

Place the target at the end so the loop does not need an i < n check on each iteration; restore the last element afterwards. Saves one comparison per step.

Complexity

• Best case O(1) (first element), worst and average O(n).
• Space O(1).

When linear search is the right choice

• Unsorted data searched only once (sorting first would cost O(n log n)).
• Very small arrays.
• Linked lists, where binary search is not possible without random access.

Note: for repeated lookups, build a HashSet/HashMap once (O(n)) and then search in O(1).

Solution and explanation

Problem

Given a sorted array and a target, return the target's index or −1.

Iterative (preferred)

static int search(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;
}

Recursive

static int searchRec(int[] a, int target, int lo, int hi) {
    if (lo > hi) return -1;
    int mid = lo + (hi - lo) / 2;
    if (a[mid] == target) return mid;
    return a[mid] < target ? searchRec(a, target, mid + 1, hi) : searchRec(a, target, lo, mid - 1);
}

Dry run

a = [1, 3, 5, 7, 9, 11], target 9: mid=2 (5) → lo=3; mid=4 (9) → found at 4.

Lower bound (first index with a[i] >= target)

static int lowerBound(int[] a, int target) {
    int lo = 0, hi = a.length;           // hi is exclusive
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] < target) lo = mid + 1; else hi = mid;
    }
    return lo;                            // insertion position
}

Complexity

• Time O(log n). Space O(1) iterative, O(log n) recursive.

Note: Java provides Arrays.binarySearch and Collections.binarySearch; they return −(insertionPoint) − 1 when the key is absent.

Solution and explanation

Problem

In a sorted array with duplicates, find the first and last index of a target.

[5, 7, 7, 8, 8, 10], target 8 → [3, 4]
target 6 → [-1, -1]

Approach 1: linear scan

Find the first match from the left and the first from the right. O(n).

Approach 2: two binary searches (optimal)

When a[mid] equals the target, record it and keep searching left (for the first) or right (for the last).

static int[] searchRange(int[] a, int target) {
    return new int[]{ find(a, target, true), find(a, target, false) };
}
static int find(int[] a, int target, boolean first) {
    int lo = 0, hi = a.length - 1, ans = -1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] == target) {
            ans = mid;
            if (first) hi = mid - 1; else lo = mid + 1;
        } else if (a[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return ans;
}

Count of occurrences

last − first + 1 (when found) – also O(log n).

Complexity

• Linear: O(n). Two binary searches: O(log n) time, O(1) space.

Solution and explanation

Problem

A sorted array of distinct values was rotated at an unknown pivot (e.g. [0,1,2,4,5,6,7] → [4,5,6,7,0,1,2]). Find the index of a target in O(log n).

Key observation

After choosing mid, at least one half (lo..mid or mid..hi) is still sorted. Check whether the target lies inside the sorted half; if yes search there, otherwise search the other half.

static int searchRotated(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;
        if (a[lo] <= a[mid]) {                                  // left half sorted
            if (target >= a[lo] && target < a[mid]) hi = mid - 1; else lo = mid + 1;
        } else {                                                // right half sorted
            if (target > a[mid] && target <= a[hi]) lo = mid + 1; else hi = mid - 1;
        }
    }
    return -1;
}

Dry run: [4,5,6,7,0,1,2], target 0

• mid=3 (7); left half [4..7] sorted, 0 not in it → lo=4.
• mid=5 (1); left half [0..1] sorted, 0 in it → hi=4.
• mid=4 (0) → found at 4.

Complexity

• Time O(log n), Space O(1). Linear search would be O(n).

Note: with duplicates (e.g. [1,0,1,1,1]) you cannot always tell which half is sorted; shrink both ends when a[lo] == a[mid] == a[hi], giving O(n) worst case.

Solution and explanation

Problem

A peak is an element greater than its neighbours (treat out-of-range neighbours as −∞). Return the index of any peak.

[1, 2, 3, 1]          → 2 (value 3)
[1, 2, 1, 3, 5, 6, 4] → 1 or 5

Approach 1: linear scan

Return the first i where a[i] > a[i+1] (or the last index). O(n).

Approach 2: binary search on the slope (optimal)

If a[mid] < a[mid+1], the values rise to the right, so a peak exists on the right; otherwise a peak exists at mid or to its left.

static int findPeak(int[] a) {
    int lo = 0, hi = a.length - 1;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] < a[mid + 1]) lo = mid + 1;   // climb uphill
        else hi = mid;
    }
    return lo;
}

Why it works

Going uphill must eventually reach a peak because the end of the array acts as −∞. Each step keeps a peak inside [lo, hi].

Complexity

• Linear: O(n). Binary search: O(log n) time, O(1) space.

Solution and explanation

Problem

Return the integer square root of n (floor of √n) without using Math.sqrt.

n = 8  → 2   (2² = 4 ≤ 8 < 9 = 3²)
n = 49 → 7

Approach 1: linear

Increase i while (i+1)² ≤ n. O(√n).

Approach 2: binary search on the answer (optimal)

The answer lies in [0, n] and mid² ≤ n is monotonic, so binary search for the largest such mid.

static int mySqrt(int n) {
    long lo = 0, hi = n, ans = 0;
    while (lo <= hi) {
        long mid = lo + (hi - lo) / 2;
        if (mid * mid <= n) { ans = mid; lo = mid + 1; }   // mid works, try larger
        else hi = mid - 1;
    }
    return (int) ans;
}

Dry run (n = 8)

• lo 0, hi 8 → mid 4 (16 > 8) → hi 3
• mid 1 (1 ≤ 8) → ans 1, lo 2
• mid 2 (4 ≤ 8) → ans 2, lo 3
• mid 3 (9 > 8) → hi 2 → stop. Answer 2.

Complexity

• Linear: O(√n). Binary search: O(log n) time, O(1) space. Newton's method converges even faster.

Note: use long for mid × mid; with int it overflows for n near Integer.MAX_VALUE.

Solution and explanation

Problem

Given two sorted arrays of sizes m and n, find the median of their combined elements in O(log(min(m, n))).

[1, 3] and [2]    → 2.0
[1, 2] and [3, 4] → 2.5

Approach 1: merge (simple)

Merge like merge sort and pick the middle. O(m + n) time and space (O(1) space if you only count to the middle).

Approach 2: binary search on the partition (optimal)

Partition both arrays so the left halves together contain half of all elements and every left element ≤ every right element. Binary search the cut position i in the smaller array; the cut in the other array is j = (m + n + 1)/2 − i.

static double findMedian(int[] a, int[] b) {
    if (a.length > b.length) return findMedian(b, a);          // search the smaller array
    int m = a.length, n = b.length, half = (m + n + 1) / 2;
    int lo = 0, hi = m;
    while (lo <= hi) {
        int i = (lo + hi) / 2, j = half - i;
        int aLeft  = i == 0 ? Integer.MIN_VALUE : a[i - 1];
        int aRight = i == m ? Integer.MAX_VALUE : a[i];
        int bLeft  = j == 0 ? Integer.MIN_VALUE : b[j - 1];
        int bRight = j == n ? Integer.MAX_VALUE : b[j];
        if (aLeft <= bRight && bLeft <= aRight) {               // correct partition
            if ((m + n) % 2 == 1) return Math.max(aLeft, bLeft);
            return (Math.max(aLeft, bLeft) + Math.min(aRight, bRight)) / 2.0;
        } else if (aLeft > bRight) hi = i - 1;                  // too many from a
        else lo = i + 1;                                        // too few from a
    }
    throw new IllegalArgumentException("Input arrays are not sorted");
}

Complexity

• Merge: O(m + n). Partition binary search: O(log(min(m, n))) time, O(1) space.

Note: this is a classic "hard" interview question; explain the partition condition before coding.