二元搜尋 - a920604a/leetcode GitHub Wiki

---

title: Binary Search tags:
- Binary Search categories: - CS - Algorithm comments: false

觀念

O(logN)，想法簡單，細節是魔鬼。溢位、mid是加一減一、while()用<= 還是<。 注意搜尋區間和while終止條件 搜尋左右邊界，只要修改nums[mid] ==target 條件處

題目

• 34 Find First and Last Position of Element in Sorted Array (Medium)
• 35 Search Insert Position (Easy)
• 209 Minimum Size Subarray Sum
• *354 Russian Doll Envelopes (Hard)
• 392 Is Subsequence (Easy)
• 658 Find K Closest Elements
• 704 Binary Search (Easy)
• 793 Preimage Size of Factorial Zeroes Function (Hard)
• 875 Koko Eating Bananas (Medium)
• 2594 Minimum Time to Repair Cars (Medium)
• 1011 Capacity To Ship Packages Within D Days (Medium)
• 1870 Minimum Speed to Arrive on Time
• 1898 Maximum Number of Removable Characters
• 2226 Maximum Candies Allocated to K Children
• 410 Split Array Largest Sum (Hard)

補充

• *4 Median of Two Sorted Arrays
• 33 Search in Rotated Sorted Array
• 81 Search in Rotated Sorted Array II
• 69 Sqrt(x)
• 153 Find Minimum in Rotated Sorted Array
• 154 Find Minimum in Rotated Sorted Array II
• 167 Two Sum II - Input Array Is Sorted
• 274 H-Index
• 275 H-Index II
• 278 First Bad Version
• *300 Longest Increasing Subsequence
• *315 Count of Smaller Numbers After Self (Hard)
• 334 Increasing Triplet Subsequence
• 374 Guess Number Higher or Lower
• 475 Heaters
• 611 Valid Triangle Number
• 633 Sum of Square Numbers
• 1283 Find the Smallest Divisor Given a Threshold
• 1894 Find the Student that Will Replace the Chalk
• 2187 Minimum Time to Complete Trips (Medium)

Binary Search 框架與變形

int binarySearch(int[] nums, int target) {
    int left = 0, right = ...;

    while(...) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            ...
        } else if (nums[mid] < target) {
            left = ...
        } else if (nums[mid] > target) {
            right = ...
        }
    }
    return ...;
}

int binarySearch(int[] nums, int target) {
    int left = 0; 
    int 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 if (nums[mid] > target)
            right = mid - 1; // 注意
    }
    return -1;
}

• 盡量不要出現else，所有情況都寫清楚。
• 終止條件left == right QA

1. 為什麼 while 迴圈條件是<= 而不是 < 因為right ＝ nums.leagth-1 ，而不是nums.length，區別相當於：前者是[left, right]，後者是[left, right)，因為索引大小為nums.length是越界的。

也可以這樣寫

//...
while(left < right) {
    // ...
}
return nums[left] == target ? left : -1;

左側邊界的二元搜尋(較普及的寫法) [1,2,2,2,3] 尋找所有２的位置

// option 1 
int left_bound(int[] nums, int target) {
    if (nums.length == 0) return -1;
    int left = 0;
    int right = nums.length; // 注意

    while (left < right) { // 注意
        int mid = (left + right) / 2;
        if (nums[mid] == target) {
            right = mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid; // 注意
        }
    }
    return left;
}

// option 2 
int left_bound(int[] nums, int target) {
    // 搜索区间为 [left, right]
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        // if else ...
    
        if (nums[mid] < target) {
            // 搜索区间变为 [mid+1, right]
            left = mid + 1;
        } else if (nums[mid] > target) {
            // 搜索区间变为 [left, mid-1]
            right = mid - 1;
        } else if (nums[mid] == target) {
            // 收缩右侧边界
            right = mid - 1;
        }
    }
    if (left >= nums.length || nums[left] != target) // 检查越界
        return -1;
    return left;
}

• 因為 while(left< right) ，終止條件left == right，搜尋區間 [left, right)
• 因為 搜尋區間 [left, right) ，會 分成兩區間 [left, mid) 和 [mid+1, right)
• 返回left 和 right 都一樣意思，因為終止條件是 left== right

右側邊界的二元搜尋

int right_bound(int[] nums, int target) {
    if (nums.length == 0) return -1;
    int left = 0, right = nums.length;

    while (left < right) {
        int mid = (left + right) / 2;
        if (nums[mid] == target) {
            left = mid + 1; // 注意
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid;
        }
    }
    
    if(l==0) return -1;  // 注意
    return nums[l-1]==target?l-1:-1;  // 注意
}

• 因為終止條件是 left== right ， 所以return left-1 和 return right-1 都一樣。
• 因為left = mid + 1; while迴圈結束時，nums[left] 一定不等於target，而nums[left-1]可能是target

統一左右兩側邊界的二元搜尋

int right_bound(int[] nums, int target) {
    int l = 0, r = nums.size()-1;
        while(l<=r){
            int mid = l + (r-l)/2;
            if(nums[mid] == target){
                // return mid;
                r = mid-1; // left bound
                // l = mid+1 ; // right bound
                    
            }
            else if(nums[mid]<target) l = mid+1;
            else r = mid -1 ;
        }
        // left bound
        if(l>= nums.size() || nums[l]!=target) return -1;
        return l;
        //right bound
        // if(r<0 || nums[r]!=target) return -1;
        // return r;
}