c++ 二分查找，数组学习

//  二分查找主要适合有规律的数组，通过不断  移动指向数组中段的指针(不断缩小目标所在区间)  
实现查找目标的目的。
在没有规律的数组中，一般用  双指针  去遍历寻找目标。

//  题目：给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，
写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

class Solution:
public:
    int search(vector& nums , int target){
        int left = 0;
        int right = nums.size() - 1;
        while(left <= right){          //这里的left<=right 主要还是与下面的middle计算方式有关
            int middle = left + ((right - left)/2);
            if(nums[middle] > target){
                right = middle - 1;
            }
            else if(nums[middle] < target){
                left = middle + 1;
            }
            else{
                return middle;
            }
        }
            return -1;
    }
};

//题目： 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。
//如果目标值不存在于数组中，返回它将会被按顺序插入的位置。 
                  输入: nums = [1,3,5,6], target = 5
                  输出: 2

class Solution {
public:
    int searchInsert(vector& nums, int target) {
        int n = nums.size();
        int left = 0;
        int right = n - 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;
            }
        }
        // 分别处理如下四种情况
        // 目标值在数组所有元素之前  [0, -1]
        // 目标值等于数组中某一个元素  return middle;
        // 目标值插入数组中的位置 [left, right]，return  right + 1
        // 目标值在数组所有元素之后的情况 [left, right]， return right + 1
        return right + 1;
    }
};

题目：在排序数组中查找目标出现的第一个位置和最后位置。
示例：
    输入：nums = [5,7,7,8,8,10]，target = 8
    输出：[3,4]

思路：
    考虑三种情况：
    1、target 不在数组的范围内 返回{-1，-1}
    2、target 在数组范围内，但是数组中没有target，返回{-1，-1}
    3、target 在数组中 返回其在数组中的位置

class Solution{
public:
    vector searchRange(vector& nums,int target){
        int leftBorder = getLeftBorder(nums, target);
        int rightBorder = getRightBorder(nums, target);
        // 情况一
        if (leftBorder == -2 || rightBorder == -2) return {-1, -1};
        // 情况三
        if (rightBorder - leftBorder > 1) return {leftBorder + 1, rightBorder - 1};
        // 情况二
        return {-1, -1};
    }
private:
    int getRightBorder(vector& nums,int target){
        int left = 0;
        int right = nums.size() - 1;
        int rightBorder = -2; //记录rightBorder没有被赋值的情况
        while(left <= right){
            int middle = left + (right-left)/2;
            if(nums[middle] > target){
                right = middle - 1;
            }
            else{
                left = middle + 1;
                rightBorder = left;
            }
        }
        return rightBorder;
    }
    
    int getLeftBorder(vector& nums,int target){
        int left = 0;
        int right = nums.size() - 1;
        int leftBorder = -2;
        while(left <= right){
            int middle = left + (right - left)/2;
            if(nums[middle] >= target){
                right = middle - 1;
                leftBorder = right;
            }
            else{
                left = middle + 1;
            }
        }
            return leftBorder;
    }
};