# Gao's LeetCode 101: Binary Search

## 0. Post Details

- Reference: [Gao et al., LeetCode 101 - A Grinding Guide, 2001.](https://noworneverev.github.io/leetcode_101/category/4-%E5%8D%83%E5%A5%87%E7%99%BE%E6%80%AA%E7%9A%84%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95)
- Post by: Jedd Yang
- Date: 2025-09-10
- Keywords: Sort

## 1. Problems

### <font color="#32CD32">69. Sqrt(x)</font>

> Given a non-negative integer `x`, return the square root of `x` rounded down to the nearest integer. The returned integer should be non-negative as well. You must not use any built-in exponent function or operator. For example, do not use `pow(x, 0.5)` in c++ or `x ** 0.5` in python.

:::warning
- Approach: Direct binary search.
- Complexity: Time $O(log(n))$; Space $O(1)$.
:::

class Solution {
public:
    int mySqrt(int x) {
        int left = 1, right = x, mid, x_div_mid;
        while (left <= right){
            mid = left + (right - left)/2;
            x_div_mid = x / mid;
            if (x_div_mid == mid){
                return mid;
            }
            if (x_div_mid > mid){
                left = mid + 1;
            }
            if (x_div_mid < mid){
                right = mid - 1;
            }
        }
        return right;
    }
};

:::success
- Approach: Newton-Raphson method.
$$
\begin{aligned}
t_{n+1} = t_n - \frac{f(t_n)}{f^{'}(t_n)} \wedge f(t)=t^{2}−x\\
\Rightarrow t_{n+1} = t_n - \frac{t_n^{2}−x}{2 t_n} = \frac{t_n + x/t_n}{2}
\end{aligned}
$$
- Complexity: Time $O(log(x))$; Space $O(1)$.
:::

class Solution {
public:
    int mySqrt(int x) {
        long t = x;
        while (t * t > x){
            t = (t + x/t)/2;
        }
        return t;
    }
};

### <font color="#FFA500">34. Find First and Last Position of Element in Sorted Array</font>

> Given an array of integers `nums` sorted in non-decreasing order, find the starting and ending position of a given `target` value. If `target` is not found in the array, return `[-1, -1]`. You must write an algorithm with `O(log n)` runtime complexity.

:::success
- Approach: Binary search.
- Complexity: Time $O(log(n))$; Space $O(1)$.
:::

class Solution {
public:
    int lowerBound(vector<int> &nums, int tgt){
        int l = 0, r = nums.size(), mid;
        while (l < r){
            mid = l + (r - l)/2;
            if (nums[mid] < tgt) {
                l = mid + 1;
            }else{
                r = mid;
            }
        }
        return l;
    }
    
    // int upperBound(vector<int> &nums, int tgt){
    //     int l = 0, r = nums.size(), mid;
    //     while (l < r){
    //         mid = l + (r - l)/2;
    //         if (nums[mid] <= tgt) {
    //             l = mid + 1;
    //         }else{
    //             r = mid;
    //         }
    //     }
    //     return l;
    // }
    
    vector<int> searchRange(vector<int>& nums, int target) {
        if (nums.empty()){
            return vector<int>{-1, -1};
        }
        
        int lower = lowerBound(nums, target);
        // int upper = upperBound(nums, target);
        int upper = lowerBound(nums, target + 1);
        int lastIndex = upper - 1;
        
        if (lower == static_cast<int>(nums.size()) || nums[lower] != target) {
            return vector<int>{-1, -1};
        }
        
        return vector<int>{lower, lastIndex};
        
    }
};

### <font color="#FFA500"> 162. Find Peak Element</font>

> A peak element is an element that is strictly greater than its neighbors. Given a 0-indexed integer array `nums`, find a peak element, and return its index. If the array contains multiple peaks, return the index to any of the peaks. You may imagine that `nums[-1] = nums[n] = -inf`. In other words, an element is always considered to be strictly greater than a neighbor that is outside the array. You must write an algorithm that runs in `O(log n)` time.

:::success
- Approach: Binary search.
- Complexity: Time $O(log(n))$; Space $O(1)$.
:::

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int len = nums.size();

        // corver case
        if (len == 1){
            return 0;
        }

        //boundary
        if (nums[0] > nums[1]){
            return 0;
        }
        if (nums[len - 1] > nums[len - 2]){
            return len - 1;
        }

        int l = 1, r = len - 2, mid;

        while (l <= r) {
            mid = l + (r - l)/2;
            if(nums[mid] > nums[mid + 1] && nums[mid] > nums[mid - 1]){
                return mid;
            }else if (nums[mid] < nums[mid + 1]){
                l = mid + 1;
            }else{
                r = mid - 1;
            }
        }
        return -1;
    }
};

### <font color="#FFA500"> 81. Search in Rotated Sorted Array II</font>

> There is an integer array `nums` sorted in non-decreasing order (not necessarily with distinct values). Before being passed to your function, `nums` is rotated at an unknown pivot index `k` (`0 <= k < nums.length`) such that the resulting array is `[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]` (0-indexed). For example, `[0,1,2,4,4,4,5,6,6,7]` might be rotated at pivot index `5` and become `[4,5,6,6,7,0,1,2,4,4]`. Given the array `nums` after the rotation and an integer target, return `true` if `target` is in `nums`, or `false` if it is not in `nums`. You must decrease the overall operation steps as much as possible.

:::success
- Approach: Modified binary search.
- Complexity: Time $O(n)$; Space $O(1)$.
:::

class Solution {
    public:
    bool search(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1, mid;

        while (left <= right) {
            mid = left + (right - left) / 2;

            if (nums[mid] == target) {
                return true;
            }

            if (nums[mid] == nums[left]) {
                ++left;
            } else if (nums[mid] == nums[right]) {
                --right;
            } else if (nums[mid] < nums[right]) {  // right ordered
                if (target > nums[mid] && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            } else {  // left ordered
                if (target < nums[mid] && target >= nums[left]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
        }
        return false;
    }
};

### <font color="#FF0000"> 4. Median of Two Sorted Arrays </font>

> Given two sorted arrays `nums1` and `nums2` of size `m` and `n` respectively, return the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

:::success
- Approach: 使用兩組雙指針 `left` & `right` 以及 `part1` & `part2`。考慮到排序後的數組且半之後左半相當於 `nums1` 左半加上 `nums2` 左半；右半相當於 `nums1` 右半加上 `nums2` 右半。我就可以用這兩組指針配合指出`nums1` 和 `nums2` 左半最大值和右半最小值。
- Complexity: Time $O(log (m + n))$; Space $O(1)$.
:::

class Solution {
   public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        if (nums1.size() > nums2.size()) {
            return findMedianSortedArrays(nums2, nums1);
        }

        int len1 = nums1.size();
        int len2 = nums2.size();
        int left = 0;
        int right = len1;

        while (left <= right) {
            int part1 = (left + right) / 2;
            int part2 = (len1 + len2 + 1) / 2 - part1;
            int maxLeft1 = (part1 == 0) ? INT_MIN : nums1[part1 - 1];
            int minRight1 = (part1 == len1) ? INT_MAX : nums1[part1];
            int maxLeft2 = (part2 == 0) ? INT_MIN : nums2[part2 - 1];
            int minRight2 = (part2 == len2) ? INT_MAX : nums2[part2];

            if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1) {
                if ((len1 + len2) % 2 == 0) {
                    return (max(maxLeft1, maxLeft2) +
                            min(minRight1, minRight2)) /
                           2.0;
                } else {
                    return max(maxLeft1, maxLeft2);
                }
            } else if (maxLeft1 > minRight2) {
                right = part1 - 1;
            } else {
                left = part1 + 1;
            }
        }

        return 0.0;
    }
};

### <font color="#FFA500"> 540. Single Element in a Sorted Array </font>

> You are given a sorted array consisting of only integers where every element appears exactly twice, except for one element which appears exactly once. Return the single element that appears only once. Your solution must run in `O(log n)` time and `O(1)` space.

:::success
- Approach: Pairs on the left side of the single element start with even number, pairs on the right side start with odd numbers, and end in even numbers. Two condition to check,
- if `nums[mid]` is the first or last number in a pair.
- if `mid` is even or odd number.
- Complexity: Time $O(log (n))$; Space $O(1)$.
:::

class Solution {
    public:
    int singleNonDuplicate(vector<int>& nums) {
        int len = nums.size();

        if (len == 1) {
            return nums[0];
        }

        int left = 0;
        int right = len - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            // edge cases
            if (mid == 0) {
                if (nums[0] != nums[1]) {
                    return nums[0];
                }
                // left = mid + 1;
                // continue;
            }

            if (mid == len - 1) {
                if (nums[len - 1] != nums[len - 2]) {
                    return nums[len - 1];
                }
                // right = mid - 1;
                // continue;
            }

            if (nums[mid] != nums[mid + 1] && nums[mid] != nums[mid - 1]) {
                return nums[mid];
            }

            if (nums[mid] == nums[mid - 1]) {
                if ((mid - 1) % 2 == 0) {
                    left = mid + 1;
                } else {
                    right = mid - 2;
                }
            }

            if (nums[mid] == nums[mid + 1]) {
                if (mid % 2 == 0) {
                    left = mid + 2;
                } else {
                    right = mid - 1;
                }
            }
        }

        return nums[left];
    }
};

### <font color="#FF0000"> 154. Find Minimum in Rotated Sorted Array II </font>

> Suppose an array of length n sorted in ascending order is rotated between `1` and `n` times. For example, the array `nums = [0,1,4,4,5,6,7]` might become:
>
> - `[4,5,6,7,0,1,4]` if it was rotated 4 times.
> - `[0,1,4,4,5,6,7]` if it was rotated 7 times.
>
> Notice that rotating an array `[a[0], a[1], a[2], ..., a[n-1]]` 1 time results in the array `[a[n-1], a[0], a[1], a[2], ..., a[n-2]]`.
>
> Given the sorted rotated array `nums` that may contain duplicates, return the minimum element of this array.
>
> You must decrease the overall operation steps as much as possible.

:::warning
- Approach: Find minimum.
- Complexity: Time $O(n)$; Space $O(1)$.
:::

// ths works for "153. Find Minimum in Rotated Sorted Array" as well
class Solution {
public:
    int findMin(vector<int>& nums) {
        return *min_element(nums.begin(), nums.end());
    }
};

To use the proper binary search,

:::success
- Approach: Binary search.
- Complexity: Time $O(n)$; Space $O(1)$.
:::

class Solution {
public:
    int findMin(vector<int>& nums) {
        int left = 0, right = nums.size() - 1, min_ele = 5000;

        while (left <= right){
            int mid = left + (right - left)/2;

            if (nums[left] == nums[right]){
                min_ele = min(min_ele, nums[left]);
                left++;
                right--;
                continue;
            }

            if (nums[left] <= nums[mid]){
                min_ele = min(min_ele, nums[left]);
                left = mid + 1;
            } else {
                min_ele = min(min_ele, nums[mid]);
                right = mid - 1;
            }

        }

        return min_ele;
    }
};