文章目录

• 一、二分
• 二、刷题

一、二分

二、刷题

LeetCode 35. 搜索插入位置 原题链接

    $(1)$ 找到满足 >=target的第一个数，如果所有数都 <=target则插入到最后一个位置；
    $(2)$ 插入的位置可能 等于 nums.size()，在插入了target元素后整个数组的长度变为 nums.size() + 1，所以两个指针的初始位置应该是 int l = 0, r = nums.size(); 而不是 int l = 0, r = nums.size() - 1；

class Solution {public:    int searchInsert(vector<int>& nums, int target) { int l = 0, r = nums.size(); // 插入的位置可能是 nums.size() while (l < r) {     int mid = l + r >> 1;     if (nums[mid] >= target) r = mid;     else l = mid + 1; } return l;    }};

LeetCode 704. 二分查找 原题链接

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

LeetCode 剑指 Offer 53 - I. 在排序数组中查找数字 I 原题链接

    $(1)$ 找到满足 >=target性质的左边界 left；
    $(2)$ 找到满足 <=target性质的有边界right；
    $(3)$ 左边界 left和右边界 right中的个数就等于 target的个数；

class Solution {public:    int search(vector<int>& nums, int target) { if (nums.empty()) return 0; int n = nums.size(); // 找到满足性质的左边界 int left = -1, right = n; int l = 0, r = n - 1; while (l < r) {     int mid = (l + r) >> 1;     if (nums[mid] >= target) r = mid;     else l = mid + 1; } if (nums[l] != target) return 0; else  {     left = l;     l = 0, r = n - 1;     while (l < r) {  int mid = (l + r + 1) >> 1;  if (nums[mid] <= target) l = mid;  else r = mid - 1;     }     right = l; } return right - left + 1;    }};