二分查找

二分查找 :flushed: O(log n)

思路

这道题目的前提是数组为有序数组，同时题目还强调数组中无重复元素，因为一旦有重复元素，使用二分查找法返回的元素下标可能不是唯一的，这些都是使用二分法的前提条件。

左闭右闭的要点

• while (left <= right) 要使用 <= ，因为left == right是有意义的，所以使用 <=
• if (nums[middle] > target) right 要赋值为 middle - 1，因为当前这个nums[middle]一定不是target，那么接下来要查找的左区间结束下标位置就是 middle - 1
• 同理if (num[middle] > target) left 要赋值为middle + 1

example code

int left = 0;
        int right = nums.size() - 1; // 定义target在左闭右闭的区间里，[left, right]
        while (left <= right) { // 当left==right，区间[left, right]依然有效，所以用 <=
            int middle = left + ((right - left) / 2);// 防止溢出 等同于(left + right)/2
            if (nums[middle] > target) {
                right = middle - 1; // target 在左区间，所以[left, middle - 1]
            } else if (nums[middle] < target) {
                left = middle + 1; // target 在右区间，所以[middle + 1, right]
            } else { // nums[middle] == target
                return middle; // 数组中找到目标值，直接返回下标
            }
        }

leetcode 34题

题目

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。

思路

1.通过一次二分查找找到target的位置，然后在此位置左右两侧扩展来找边界
代码如下：

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) 
    {
        int middle;
        int left = 0;
        int right = nums.size() - 1;
        int maybe, t_left, t_right;
        while(left <= right)
        {
            middle = (left + right)/2;
            if(nums[middle] == target)
            {
                maybe = middle;
                break;
            }
            else if(nums[middle] < target)
                left = middle + 1;
            else if (nums[middle] > target)
                right = middle - 1;
            
        }
        if(middle != maybe)//没找到
            return vector<int>{-1,-1};
        t_left = maybe;
        t_right = maybe;
        //对目标值左右进行扩展
        while ( maybe > 0 && nums[maybe] == nums[maybe - 1])//注意&&前后语句的顺序有区别
        {
            t_left = maybe - 1;
            maybe -= 1;
        }
        maybe = t_right;
        while (maybe < nums.size() - 1 && nums[maybe] == nums[maybe + 1])
        {
            t_right = maybe + 1;
            maybe += 1;
        }
        return vector<int>{t_left,t_right};
    }
};

2.通过两次二分查找分别找target的左，右边界
代码如下：

//通过两次二分法找target的左右边界
class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
    int left = 0;
    int right = nums.size() - 1;
    int first = -1;
    int last = -1;
    // 找最左侧等于target的位置
    while (left <= right) {
      int middle = (left + right) / 2;
      if (nums[middle] == target) {
        first = middle;
        right = middle - 1; //重点 缩小范围，看还有没有等于target的数
      } else if (nums[middle] > target) {
        right = middle - 1;
      } else {
        left = middle + 1;
      }
    }

    //找最右侧等于target的位置
    left = 0;
    right = nums.size() - 1;
    while (left <= right) {
      int middle = (left + right) / 2;
      if (nums[middle] == target) {
        last = middle;
        left = middle + 1; //重点 当nums[middle] == target的时候，更新left
      } else if (nums[middle] > target) {
        right = middle - 1;
      } else {
        left = middle + 1;
      }
    }

    return {first, last};
    }
};