Algo_6_BinarySearch

學習算法

Binary Search 核心

mid區間

(left+right)/2 當left和right為大數容易overflow
left + (right-left)/2 推薦
(left+right) >> 1 當left和right為大數容易overflow

核心模板

不用check單純找數字

int main(){
  vector<int> nums;
  int l = 0;
  int r = nums.size()-1;
  while(l <= r){
    int mid = l + (r-l)/2;
    if(nums[mid] > target) r = mid - 1;
    else l = mid + 1;
    // ...  
  }
  // ...
}
 
- 需要check
 
```c++
bool check(){
  // ...
}
 
int main(){
  int l = 0;
  int r = nums.size();
  while(l <= r){
    int mid = l + (r-l)/2;
    if(check(mid)) r = mid;
    else l = mid + 1;
  }
}

為非遞增單調序列
- 判斷右邊的數大小再做搜尋

int binSearch(vector<int>& nums,int l,int r){
  int mid = l + (r-l)/2; 
  if(nums[mid] > nums[r]) return binSearch(nums,mid+1,r);
  if (nums[l] > nums[mid]) return binSearch(nums,l,mid);
}

Leetcode 367

class Solution {
public:
    bool isPerfectSquare(int num) {
        if(num == 0) return false;
        if(num == 1) return true;
        int l = 1;
        int r = num;
        while(l <= r){
            int mid = l + (r-l)/2;
            if(num % mid == 0 && mid == num/mid){
                return true;
            }else if(mid > num/mid){
                r = mid-1;
            }else{
                l = mid+1;
            }
        }
        return false;
    }
};

Leetcode 74

第一種解法，題目給的為遞增2D，使用線性搜

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int rows = matrix.size();
        int col = matrix[0].size()-1;
        int row = 0;
        while(row < rows && col > -1){
            int cur = matrix[row][col];
            if(cur == target) return true;
            if(cur > target) col--;
            else row++;
        }
        return false;
    }
};

第二種使用BinarySearch

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int row = matrix.size();
        int col = matrix[0].size();
        int start = 0;
        int end = row*col -1;
        while(start <= end){
            int mid = start + (end-start)/2;
            if(matrix[mid/col][mid%col] == target) return true;
            else if(matrix[mid/col][mid%col] > target) end = mid-1;
            else start = mid+1;
        }
        return false;
    }
};

2D特別處理方法

對於所有的2D皆可用 mid/col 表示x，mid%col 表示y

Leetcode 153

此題為非遞增單調序列

class Solution {
public:
    int binarySearch(vector<int>& nums,int l,int r){
        int mid = l + (r-l)/2;
        if(nums[r] < nums[mid]){
            return binarySearch(nums,mid+1,r);
        }
        if(nums[l] > nums[mid]){
            return binarySearch(nums,l,mid);
        }
        return nums[l];
    }
    int findMin(vector<int>& nums) {
        return binarySearch(nums,0,nums.size()-1);    
    }
};

Leetcode 875

class Solution {
public:
    bool check(vector<int>& piles,int k,int h){
        long int hours = 0;
        for(int p : piles){
            int tmp = p / k;
            hours += tmp;
            if(p % k != 0) hours ++;
        }
        return hours <= h;
    }
    int minEatingSpeed(vector<int>& piles, int h) {
        int l = 1;
        int r = 1000000000;
        while(l <= r){
            int mid = l + (r-l)/2;
            if(check(piles,mid,h)) r = mid-1;
            else l = mid+1;
        }
        return l;
    }
};