算法基础——二分查找（一）

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

数组有序

查找相同元素，在数组的开始与结束位置

利用二分法，缩小每次查询的范围，减少查询次数

每次比较的元素是该段区间的中间元素，当有大小差异时，可以调整区间的左右取值，继续下一次循环

当找到相同的元素，由于可能不止一个，初始化一个目前指针作为开始、结束的结果数组，然后分别向左、向右遍历，确定目标元素的开始、结束位置

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while(left <= right) {
            int temp = left + (right - left) / 2;//防止数值大于int类型的最大值 2^32
            if(nums[temp] == target) {//找到了一个
                int start = temp - 1;//开始指针
                int end = temp + 1;//结束指针
                int[] ans = new int[] {temp, temp};//结果数组，初始值都为temp，不可为0
                while(start >= 0 && nums[start] == target) {//当start下标的元素还是target
                    ans[0] = start--;//存入结果数组，再自减
                }
                while(end < nums.length && nums[end] == target) {
                    ans[1] = end++;//存入结果数组，再自增
                }
                return ans;
            }
            if(nums[temp] > target) {//target在区间的左边，改变右指针
                right = temp - 1;
            } else {//target在区间的右边，改变左指针
                left = temp + 1;
            }
        }
        return new int[] {-1,-1};
    }
}

二、搜索旋转排序数组

感觉为了出题而出题

直接遍历也可以解体

用二分法，但是每个区间都要查询一番，除非找到了才结束

递归二分法：

结束条件：找到target，或者下标交叉

递归：分别递归查找左区间、右区间，返回一个查找区间得到的最大值，实际上（-1和结果下标的比较）

class Solution {
    public int search(int[] nums, int target) {
        return searchHelper(nums, target, 0, nums.length - 1);
    }

    private int searchHelper(int[] nums, int target, int left, int right) {
        if(left > right) {//下标交叉
            return -1;
        }
        int temp = left + (right - left) / 2;
        if(nums[temp] == target) {//找到target
            return temp;
        }
        //-1、结果下标的最大值
        return Math.max(searchHelper(nums, target, left, temp - 1), searchHelper(nums, target, temp + 1, right));
    }
}

三、搜索二维矩阵

两次二分查找

先二分查找确定目标所在行，再在行内二分查找其列下标

由题可知：列的元素是升序、行的元素是升序

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int start = 0;
        int end = matrix.length - 1;
        //确定目标的行
        while(start <= end) {
            int temp = start + (end - start) / 2;
            if(matrix[temp][0] == target) {
                return true;
            }
            if(matrix[temp][0] > target) {
                end = temp - 1;
            } else {
                start = temp + 1;
            }
        }
        int row = end;//在确定行寻找
        if(row >= 0 && row < matrix.length) {
            end = matrix[row].length - 1;
            start = 0;
            while(start <= end) {
                int temp = start + (end - start) / 2;
                if(matrix[row][temp] == target) {
                    return true;
                }
                if(matrix[row][temp] > target) {
                    end = temp - 1;
                } else {
                    start = temp + 1;
                }
            }
        }
        return false;
    }
}