二分查找的通用板子，需要注意理解：

ep：1，2，2，2，3，5
//查大于等于target的第一个位置, target=2，目标位置是1
int l = 0, r = n - 1;
while (l < r) {
    int mid = l + r >> 1;
    // 找最早的那个值，nums[mid] >= x时，即使等于目标值，也要继续向左找，所以 r = mid
    // 这里用 r = mid 而不是 r = mid - 1，因为 mid可能是我们要找的左边界
    if(a[mid] >= x) r=mid;
    else l = mid + 1;
}

//查小于等于target的最后一个位置，target等于2，目标位置是3
int l = 0, r = n - 1;
while (l < r)
 {
        int mid = l + r + 1 >> 1;
        // 找最晚的那个值，nums[mid] <= x时，即使等于目标值，也要继续向右找，所以 l = mid
    	// 这里用 l = mid而不是 l = mid + 1，因为 mid可能是我们要找的右边界
        if (a[mid] <= x) l = mid;
        else r = mid - 1;
 }

搜索插入位置

转化思路，nums[pos−1]<target≤nums[pos]，找pos，可以变成找第一个大于target的pos（acwing 查找不小于target的第一个位置）。代码同上面的模板。

搜索二维矩阵

找到最后一个不大于目标数的那一行，再对那一行进行二分查找。
也可以用思维方式，从左下角出发，比target大就向上走，反之向右走。更简单。

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m=matrix.size(),n=matrix[0].size();
        int row=m-1,col=0;
        while(row>=0&&col<n){
            if(matrix[row][col]==target)return true;
            else if(matrix[row][col]>target)row--;
            else col++;
        }
        return false;
    }
};

在排序数组中查找元素的第一个和最后一个位置

同第一题。套两个模板。

搜索旋转数组

变种二分查找，虽然被打乱了一些顺序，但是还是可以分两部分看有序的，nums[0] <= nums[mid]，代表左边是有序的，否则右边是有序的。

class Solution {
    public int search(int[] nums, int target) {
        int n = nums.length;
        if(n == 0){
            return -1;
        }
        if(n == 1){
            return nums[0] == target? 0:-1;
        }
        int l = 0;
        int r = n - 1;
        while(l <= r){
            int mid = (l + r) / 2;
            if(nums[mid] == target){
                return mid;
            }
            // 左边有序
            if(nums[0] <= nums[mid]){
                if(nums[0] <= target && target < nums[mid]){
                    r = mid - 1;
                }else{
                    l = mid + 1;
                }
            }else{
                    if(nums[n-1] >= target && target > nums[mid]){
                        l = mid + 1;
                    }else{
                        r = mid - 1;
                    }
                }
            }
                    return -1;
        
    }
}

寻找旋转排序数组中的最小值

同4题，也是区分左右两边的有序性判断性质。如果左边有序，最小值肯定是最左的，如果右边有序，最小值肯定是nums[mid].

class Solution {
    public int findMin(int[] nums) {
        if(nums.length == 1) return nums[0];
        int minV = nums[0];
        int l = 0;
        int r = nums.length - 1;
        while(l <= r){
            int mid = (l + r) / 2;
            if(nums[mid] < minV) minV = nums[mid];
            // 左边有序
            if(nums[mid] >= nums[0]){
                minV = nums[0] < minV? nums[0]:minV;
                l = mid + 1;
            }else{
                minV = nums[mid] < minV? nums[mid]:minV;
                r = mid - 1;
            }
        }
        return minV;
    }
}

寻找两个正序数组的中位数

难。

力扣题解：https://leetcode.cn/problems/median-of-two-sorted-arrays/solutions/3660794/deepseekti-jie-by-elk-r-xscq 将问题转化为在两个数组中寻找合适的分割线，使得分割线左边的所有元素都小于等于右边的所有元素，并且左右两边的元素数量相等或左边多一个。

确保第一个数组是较短的：这样我们可以将时间复杂度优化到O(log(min(m,n)))
定义分割线：分割线将数组分为左右两部分
对于数组A，分割线在i的位置，左边有i个元素，右边有m-i个元素
对于数组B，分割线在j的位置，左边有j个元素，右边有n-j个元素

理想分割条件：
A[i-1] ≤ B[j] 且 B[j-1] ≤ A[i]（左边最大值 ≤ 右边最小值）
关于A[i-1] ≤ B[j] 且 B[j-1] ≤ A[i]（左边最大值 ≤ 右边最小值），这个式子的意义在于：
找出来的i和j，一定是这样的序列（A[i-1],B[j-1]的顺序不重要，可以互换，重点在于i和j一定是紧挨着的）：....A[i-1],B[j-1], A[i],B[j]，所以一定会有：A[i-1] ≤ B[j] 且 B[j-1] ≤ A[i]
注意，此处的i，j表示的并不是下标，而是有多少个数，在左边，在右边。

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        // 确保 nums1 是较短的数组
        if (nums1.length > nums2.length) {
            int[] temp = nums1;
            nums1 = nums2;
            nums2 = temp;
        }
        
        int m = nums1.length;
        int n = nums2.length;
        int imin = 0, imax = m, halfLen = (m + n + 1) / 2;
        
        while (imin <= imax) {
            int i = (imin + imax) / 2;
            int j = halfLen - i;
            
            if (i < m && nums2[j - 1] > nums1[i]) {
                // i 太小，需要增大
                imin = i + 1;
            } else if (i > 0 && nums1[i - 1] > nums2[j]) {
                // i 太大，需要减小
                imax = i - 1;
            } else {
                // 说明找到合适的分割线了，开始计算中位数
                
                // 计算左半部分的最大值
                int maxOfLeft;
                if (i == 0) {
                    // i==0 说明没有任何num1的元素在左边，此时的序列应该是：...j-1, i, j...左半部最小值只能是j-1 此处的i并不是下标 而是表示num1数组有多少个元素在左边
                    maxOfLeft = nums2[j - 1];
                } else if (j == 0) {
                    maxOfLeft = nums1[i - 1];
                } else {
                    maxOfLeft = Math.max(nums1[i - 1], nums2[j - 1]);
                }
                
                // 如果总长度是奇数，直接返回左半部分最大值
                if ((m + n) % 2 == 1) {
                    return maxOfLeft;
                }
                
                // 计算右半部分的最小值
                int minOfRight;
                if (i == m) {
                    // 同理 i==m，说明num1的所有元素全在左边，右边没有任何元素，右边的那个值只能取nums2[j]
                    minOfRight = nums2[j];
                } else if (j == n) {
                    minOfRight = nums1[i];
                } else {
                    minOfRight = Math.min(nums1[i], nums2[j]);
                }
                
                // 如果总长度是偶数，返回平均值
                return (maxOfLeft + minOfRight) / 2.0;
            }
        }
    }
}