List-binarysearch

二分查找

leetcode.704

• 鏈接https://leetcode.cn/problems/...

• 解題方法：二分查找模板（有序數組）

  bool check(int x) // 檢查x是否滿足某種性質
  int bsearch_1(int l, int r){
    while (l < r){
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    return l;
  }
  
  int bsearch_2(int l, int r){
    while (l < r){
        int mid = l + r + 1>> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
  }

• leetcode解題代碼

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

• ACM模式調試

輸入
第一行輸入兩個數n，target
n表示數組中數的個數，target表示目標值
第二行表示數組

5 9
-1 0 3 5 9 12

輸出

4

調試代碼

#include <iostream>
#include <vector>

using namespace std;

int main(){
    int n, target;
    vector<int> nums(6);
    cin >> n >> target;
    for (int i = 0; i < n; i ++) cin >> nums[i];
    
    int l = 0, r = nums.size() - 1;
    while (l < r){
        int mid = (l + r) / 2;
        if (nums[mid] >= target) r = mid;
        else l = mid + 1;
    }
    if (nums[l] == target) cout << l;
    else cout << -1;
    return 0;
}

leetcode.35

• 鏈接https://leetcode.cn/problems/...
• 解題方法：注意這裏與上一題的區別在於需要特判，如果目標值大於數組最後一位則返回數組長度

• leetcode解題代碼

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

• ACM模式調試 和上題類似

leetcode.69

• 鏈接https://leetcode.cn/problems/...
• 解題方法：本題題意類似於找到最大的y使得y^2<=x，所以使用第二個模板

• leetcode解題代碼

  class Solution {
  public:
    int mySqrt(int x) {
        long l = 0, r = x;// long防止越界
        while (l < r){
            int mid = l + r + 1 >> 1;
            if (mid <= x / mid) l = mid;// mid * mid會越界
            else r = mid - 1;
        }
        return r;
    }
  };

• ACM模式調試

輸入一個數x

4

輸出

2

調試代碼

#include <iostream>

using namespace std;

int main(){
    int x;
    cin >> x;
    
    long l = 0, r = x;// long防止越界
    while (l < r){
        int mid = l + r + 1 >> 1;
        if (mid <= x / mid) l = mid;// mid * mid會越界
        else r = mid - 1;
    }
    cout << r << endl;
    return 0;
}

leetcode.367

• 鏈接https://leetcode.cn/problems/...
• 解題方法：與上題類似，注意數組越界

• leetcode解題代碼

  class Solution {
  public:
    bool isPerfectSquare(int num) {
        long l = 1, r = num;
        while (l < r){
            int mid = l + r + 1 >> 1;
            if (mid <= num / mid) l = mid;
            else r = mid - 1;
        }
        return r * r == num;
    }
  };

• ACM模式調試代碼 和上題類似

leetcode.34

• 鏈接https://leetcode.cn/problems/...
• 解題方法：找到數組的二段性，利用模板一找到左側第一個target的下標，利用模板二找到右側最後一個target的下標
  對於第一個target，[5, 7, 7, 8]，nums[mid] < target
  對於最後一個target，[8, 10]，nums[mid] > target

• leetcode解題代碼

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

• ACM模式調試

輸入
第一行輸入兩個數n，target
n表示數組中數的個數，target表示目標值
第二行表示數組

6 8
5 7 7 8 8 10

輸出

3 4 

調試代碼

#include <iostream>
#include <vector>
using namespace std;

int main(){
    int n, target;
    vector<int> nums(6);
    cin >> n >> target;
    for (int i = 0; i < n; i ++) cin >> nums[i];
    
    vector<int> res;
    int l = 0, r = nums.size() - 1;
    while (l < r)
    {
        int mid = (l + r) / 2;
        if (nums[mid] < target) l = mid + 1;
        else r = mid;
    }
    if (nums[l] != target) cout << -1 << -1 << endl;
    res.push_back(l);
    int L = l;

    l = 0, r = nums.size() - 1;
    while (l < r)
    {
        int mid = (l + r + 1) / 2;
        if (nums[mid] > target) r = mid - 1;
        else l = mid;
    }
    res.push_back(l);
    for (auto c: res){
        cout << c << ' ';
    }
    return 0;
}

解題參考：https://www.acwing.com/
刷題順序：https://www.programmercarl.com/