Searching Algorithms

Binary Search is the most important — O(log n) on sorted data. Template: define search space, shrink by half each step. Variations: find leftmost/rightmost occurrence, search in rotated array, search on answer space (minimize/maximize). Always check: is the array sorted? Can I binary search on the answer?

Key Concepts

Deep Dive: Binary Search Templates

Standard binary search:

public int binarySearch(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) return mid;
        else if (nums[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

Find leftmost (first) occurrence:

public int findFirst(int[] nums, int target) {
    int left = 0, right = nums.length - 1, result = -1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) { result = mid; right = mid - 1; }
        else if (nums[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return result;
}

Binary search on answer (minimize/maximize):

// Find minimum value that satisfies condition
int left = minAnswer, right = maxAnswer;
while (left < right) {
    int mid = left + (right - left) / 2;
    if (condition(mid)) right = mid;
    else left = mid + 1;
}
return left;

Deep Dive: Search in Rotated Sorted Array

public int search(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) return mid;
        if (nums[left] <= nums[mid]) {  // Left half sorted
            if (target >= nums[left] && target < nums[mid]) right = mid - 1;
            else left = mid + 1;
        } else {  // Right half sorted
            if (target > nums[mid] && target <= nums[right]) left = mid + 1;
            else right = mid - 1;
        }
    }
    return -1;
}

Common Interview Questions

• Binary Search
• Search in Rotated Sorted Array
• Find First and Last Position of Element
• Search a 2D Matrix
• Koko Eating Bananas (binary search on answer)
• Median of Two Sorted Arrays
• Find Peak Element