Sunday, June 29, 2025

LeetCode - Binary Search Problems

 

📘 5. LeetCode Problems Using Binary Search


✅ Easy

1. 704. Binary Search

Question: Given an array of integers nums which is sorted in ascending order, and an integer target, return the index if the target is found. If not, return -1.

Brute Force:

int search(vector<int>& nums, int target) {
    for (int i = 0; i < nums.size(); ++i)
        if (nums[i] == target) return i;
    return -1;
}

Time Complexity: O(n)

Optimal (Binary Search):

int search(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 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;
}

Time Complexity: O(log n)

Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4

Iteration Table:

Left Right Mid nums[Mid] Comparison
0 5 2 3 3 < 9 → move right
3 5 4 9 Found!

2. 35. Search Insert Position

Question: Given a sorted array and a target value, return the index if found. If not, return the index where it would be if it were inserted in order.

Brute Force:

int searchInsert(vector<int>& nums, int target) {
    for (int i = 0; i < nums.size(); ++i)
        if (nums[i] >= target) return i;
    return nums.size();
}

Time Complexity: O(n)

Optimal (Binary Search):

int searchInsert(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 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 left;
}

Input: nums = [1,3,5,6], target = 5
Output: 2

Iteration Table:

Left Right Mid nums[Mid] Comparison
0 3 1 3 3 < 5 → L=2
2 3 2 5 Found

3. 278. First Bad Version

Question: Given n versions [1, 2, ..., n] and an API isBadVersion(version) returns whether version is bad. Find the first bad version.

Optimal (Binary Search):

int firstBadVersion(int n) {
    int left = 1, right = n;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (isBadVersion(mid)) right = mid;
        else left = mid + 1;
    }
    return left;
}

Input: n = 5, first bad = 4
Output: 4

Iteration Table:

Left Right Mid isBadVersion Next
1 5 3 false left = 4
4 5 4 true right = 4
Left == Right → Return 4

✅ Medium

4. 33. Search in Rotated Sorted Array

Question: Search target in rotated sorted array with distinct elements.

Optimal:

int search(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (nums[mid] == target) return mid;
        if (nums[left] <= nums[mid]) {
            if (nums[left] <= target && target < nums[mid]) right = mid - 1;
            else left = mid + 1;
        } else {
            if (nums[mid] < target && target <= nums[right]) left = mid + 1;
            else right = mid - 1;
        }
    }
    return -1;
}

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

5. 162. Find Peak Element

Question: Find index i such that nums[i] > nums[i-1] && nums[i] > nums[i+1].

Optimal:

int findPeakElement(vector<int>& nums) {
    int left = 0, right = nums.size() - 1;
    while (left < right) {
        int mid = (left + right) / 2;
        if (nums[mid] > nums[mid + 1]) right = mid;
        else left = mid + 1;
    }
    return left;
}

Input: nums = [1,2,3,1]
Output: 2

The goal is to find an index i where nums[i] > nums[i-1] && nums[i] > nums[i+1].

🔁 Iteration Table:

Iterationleftrightmidnums[mid]nums[mid+1]ComparisonAction
1031232 < 3left = mid+1 (left = 2)
2232313 > 1right = mid (right = 2)

🔚 Final State:

left == right == 2 → Return index 2
➡️ Output: 2

This is the peak element satisfying the condition:
nums[2] = 3 > nums[1] = 2 && nums[2] = 3 > nums[3] = 1

6. 153. Find Minimum in Rotated Sorted Array

int findMin(vector<int>& nums) {
    int left = 0, right = nums.size() - 1;
    while (left < right) {
        int mid = (left + right) / 2;
        if (nums[mid] > nums[right]) left = mid + 1;
        else right = mid;
    }
    return nums[left];
}

Input: nums = [3,4,5,1,2]
Output: 1

We want to find the minimum element in the rotated sorted array.

🔁 Iteration Table:

Iterationleftrightmidnums[mid]nums[right]ComparisonAction
1042525 > 2left = mid + 1 → 3
2343121 < 2right = mid → 3

🔚 Final State:

left == right == 3 → Return nums[3] = 1

➡️ Output: 1

7. 34. Find First and Last Position of Element in Sorted Array

vector<int> searchRange(vector<int>& nums, int target) {
    int first = -1, last = -1;
    // First occurrence
    int l = 0, r = nums.size() - 1;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (nums[mid] >= target) r = mid - 1;
        else l = mid + 1;
        if (nums[mid] == target) first = mid;
    }
    // Last occurrence
    l = 0, r = nums.size() - 1;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (nums[mid] <= target) l = mid + 1;
        else r = mid - 1;
        if (nums[mid] == target) last = mid;
    }
    return {first, last};
}

Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]

🔍 Step 1: Find First Occurrence

while (l <= r) {
    int mid = (l + r) / 2;
    if (nums[mid] >= target) r = mid - 1;
    else l = mid + 1;
    if (nums[mid] == target) first = mid;
}
Iteration l r mid nums[mid] Comparison Action first
1 0 5 2 7 7 < 8 → move right l = mid + 1 → l = 3 -1
2 3 5 4 8 8 >= 8 r = mid - 1 → r = 3 4
3 3 3 3 8 8 >= 8 r = mid - 1 → r = 2 3

✅ first = 3

🔍 Step 2: Find Last Occurrence

while (l <= r) {
    int mid = (l + r) / 2;
    if (nums[mid] <= target) l = mid + 1;
    else r = mid - 1;
    if (nums[mid] == target) last = mid;
}
Iteration l r mid nums[mid] Comparison Action last
1 0 5 2 7 7 < 8 → move right l = mid + 1 → l = 3 -1
2 3 5 4 8 8 <= 8 l = mid + 1 → l = 5 4
3 5 5 5 10 10 > 8 r = mid - 1 → r = 4 4

✅ last = 4

✅ Final Output:

{3, 4}

 

✅ Hard

8. 410. Split Array Largest Sum

Question: Split array into k subarrays such that the largest sum among these is minimized.

Optimal (Binary Search on Answer):

bool isValid(vector<int>& nums, int maxSum, int k) {
    int cnt = 1, currSum = 0;
    for (int n : nums) {
        if (currSum + n > maxSum) {
            ++cnt;
            currSum = n;
        } else currSum += n;
    }
    return cnt <= k;
}

int splitArray(vector<int>& nums, int k) {
    int left = *max_element(nums.begin(), nums.end());
    int right = accumulate(nums.begin(), nums.end(), 0);
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (isValid(nums, mid, k)) right = mid;
        else left = mid + 1;
    }
    return left;
}

Input: nums = [7,2,5,10,8], k = 2
Output: 18

9. 1231. Divide Chocolate

Question: Like problem 410 but maximize minimum sweetness among k+1 pieces.

bool canDivide(vector<int>& sweetness, int k, int minSweet) {
    int count = 0, curr = 0;
    for (int s : sweetness) {
        curr += s;
        if (curr >= minSweet) {
            count++;
            curr = 0;
        }
    }
    return count >= k + 1;
}

int maximizeSweetness(vector<int>& sweetness, int k) {
    int left = 1, right = accumulate(sweetness.begin(), sweetness.end(), 0);
    while (left < right) {
        int mid = left + (right - left + 1) / 2;
        if (canDivide(sweetness, k, mid)) left = mid;
        else right = mid - 1;
    }
    return left;
}

Input: sweetness = [1,2,3,4,5,6,7,8,9], k = 5
Output: 6

 
at

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)

LeetCode C++ Cheat Sheet June

🎯 Core Patterns & Representative Questions 1. Arrays & Hashing Two Sum – hash map → O(n) Contains Duplicate , Product of A...