c++ || 二分查找

二分查找

• 二分查找需要的条件
  1.用于查找的内容逻辑上来讲是需要有序的
  2.查找的数量只能是一个，不是多个
• 二分法中关注的问题
  1.while循环中left和right的关系，到底是left<=right还是left 2.迭代过程中mid和right的关系，到底是right=mid-1，还是right= mid；

对于[left,right]（左闭右闭区间）

• 循环条件要使用while(left <= right)，因为当(left == right)这种情况发生的时候，得到的结果是有意义的
• if(nums[middle] > target) ， right 要赋值为 middle - 1， 因为当前的 nums[middle] 一定不是 target ，需要把这个 middle 位置上面的数字丢弃，那么接下来需要查找范围就是[left, middle - 1]

对于[left,right)（左闭右开区间）

• 循环条件使用while (left < right)
• if (nums[middle] > target)， right = middle，因为当前的 nums[middle] 是大于 target 的，不符合条件,不能取到 middle，并且区间的定义是 [left, right)，刚好区间上的定义就取不到 right, 所以 right 赋值为 middle。

无重复数字的升序数组的二分查找

• 问题：在一个元素升序的，无重复数字的整型数组nums和目标值target，目标值存在返回下标，不存在返回-1
• 分析：数组为空 返回-1；用中点值作为一个标杆，将整个数组分为两个区间，目标值与中点值比较就能知道它会在哪个区间，这就是分治的思维
• 步骤：
  step 1：从数组首尾开始，每次取中点值。
  step 2：如果中间值等于目标即找到了，可返回下标，如果中点值大于目标，则中间值向右的所有数字都大于目标值，全部排除。如果中点值小于目标值，则说明中间数字向左的所有数字都小于目标值，全部排除。
  step 3：根据比较进入对应的区间，直到区间左右端相遇，意味着没有找到。

    int search(vector<int>& nums, int target) {
   
        // write code here
        if(nums.empty()) return -1; //为空 -1
        int left=0; //左闭
        int right = nums.size()-1; //右闭
        while(left <= right)   //<=
        {
   
             int mid = (left+right)/2;
            if(nums[mid]==target)
            {
   
                return mid;
            }
            if(target < nums[mid])
             right=mid-1; //mid-1
            else left=mid + 1;
        }
        return -1;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

      int search(vector<int>& nums, int target) {
   
        // write code here
        if(nums.empty()) return 
1
2
3