2/7 算法每日N题（二分+双指针）

第一题：

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

第一题没什么细节，用笔在纸上画一下模拟一下即可

第二题：

这一道题相对其他题比较抽象，具体体现在其最后一个位置不好找，因为在编译的时候，计算mid时系统会自动向下取整，因此在处理左端点时可以向下取整得到，处理又端点时需要向上取整，同时要注意数据的溢出，这里是如何处理的。

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

我绝得这个题最关键的步骤就是，nums[mid]与target是否取等，在求开始位置的时候，不用取等，原因是else成立条件为>=那么right所指向的未必是最右边的那个元素，因为可能有重复元素，对于求最后位置时，else条件为>的目的是，使得right所指向的目标元素为最后的位置。

第三题：

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

1. 判断中间位置的值 nums[mid] 与目标值 target 的大小关系：
   • 若 nums[mid] < target，说明目标值在右半部分，将 l 更新为 mid+1。
   • 若 nums[mid] >= target，说明目标值在左半部分或者等于中间值，将 r 更新为 mid-1。
2. 循环结束后，返回 l，即为目标值在数组中的插入位置

第四题：

整数平方根最小为1，最大为本身，因此左指针指在1，右指针指在r，防止mid*mid的值溢出，将数据类型设为long long 类型

在这个平方根求解算法中，向上取整（即计算中点时使用的 mid = l + (r - l + 1) / 2 而不是 mid = l + (r - l) / 2）的主要原因是为了确保二分查找过程能够正确地收敛，特别是在处理左右边界相邻但还未找到确切平方根整数值的情况下。

这个细节主要影响的是当左边界（l）和右边界（r）相邻时的行为。常规的二分查找中点计算（向下取整）可能会导致在某些情况下循环不能正确终止，进而错过正确答案。具体到这个问题：

第五题：

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

山脉即大于左右两边的山，暴力也可求解

class Solution {
public:
	int peakIndexInMountainArray(vector<int>& arr) {
		int n = arr.size();
		// 遍历数组内每⼀个元素，直到找到峰顶
		for (int i = 1; i < n - 1; i++)
			// 峰顶满⾜的条件
			if (arr[i] > arr[i - 1] && arr[i] > arr[i + 1])
				return i;
		// 为了处理 oj 需要控制所有路径都有返回值
		return -1;
	}
}