力扣top100-二分

二分

35.搜索插入位置

35. 搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。请必须使用时间复杂度为 O(log n) 的算法。

解法

​ 二分查找模板

class Solution {
    public int searchInsert(int[] nums, int target) {
        int l = 0, r = nums.length - 1;
        //初始的搜索范围是整个数组，左右边界分别是 left 和 right。如果我们在搜索过程中设定了 left < right 作为循环条件，
        //那么当 left 等于 right 时，循环将终止，此时还未检查该位置的元素。设定为 left <= right 可以确保在每次缩小搜索范围时，
        //仍然包含当前范围的所有可能位置，最终检查所有可能的位置。
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] < target) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return l;
    }
}

74. 搜索二维矩阵

74. 搜索二维矩阵

给你一个满足下述两条属性的 m x n 整数矩阵：

• 每行中的整数从左到右按非严格递增顺序排列。
• 每行的第一个整数大于前一行的最后一个整数。

给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出：true

解法

​ 其实和最基础的二分很像，就是加了个二维数组的下标

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length, n = matrix[0].length;
        int l = 0, r = m * n - 1;
        while (l <= r) {
            int mid = (l + r) / 2;
            int row = mid / n;
            int col = mid % n;
            if (target > matrix[row][col]) {
                l = mid + 1;
            } else if (target < matrix[row][col]) {
                r = mid - 1;
            } else {
                return true;
            }
        }
        return false;
    }
}

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

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

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target，返回 [-1, -1]。你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

解答：还是利用最基本的二分。

class Solution {
    public int[] searchRange(int[] nums, int target) {
        //找到第一个小于target的位置和第一个大于target的位置
        int n = nums.length;
        if (n == 0) {
            return new int[] {-1, -1};
        }
        //在数组中找到第一个大于等于target的目标
        int a = searchInsert(nums, target);

        //在一个有序数组中找第一个大于等于 target+1的下标 就相当于找到最后一个大于target的下标
        int b = searchInsert(nums, target + 1) - 1;
        
        if (a > b) {    //  数组中不存在target
            return new int[] {-1, -1};
        }
        return new int[] {a, b};
    }

    public int searchInsert(int[] nums, int target) {
        //left左边的部分全部小于target，并以right结尾；right右边的部分全部大于等于target，并以left为首
        int l = 0, r = nums.length - 1;
        while (l <= r) {
            int mid = l + (r - l)/2;
            if (nums[mid] < target) {
                l = mid + 1;
            } else { //在一个有序数组中找第一个大于等于 target的下标
                r = mid - 1;
            }
        }
        return l;
    }
}

class Solution {
    public int search(int[] nums, int target) {
        int n = nums.length;
        if (n == 0) {
            return  -1;
        }
        int l = 0, r = n - 1;
        while(l <= r) {
            int mid = (l + r) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            //这里必须是>=  防止出现这样的情况：[3,1]
            if (nums[mid] >= nums[l]) {  //前半部分有序
                if (nums[l] <= target && target < nums[mid]) {  //如果target在前半部分
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            } else{
                if (nums[mid] < target && target <= nums[r]) { //如果target在后半部分
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
        }
        return -1;
    }
}

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

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

已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：

• 若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
• 若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]

注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。

给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。你必须设计一个时间复杂度为 O(log n) 的算法解决此问题

解答：

class Solution {
    public int findMin(int[] nums) {
        int l = 0, r = nums.length - 1;
        while (l < r) {         //l == r直接退出返回最小值
            int mid = (l + r) / 2;
            if (nums[mid] > nums[r]) {  //中间的值大于最右值  最小值在右半边
                l = mid + 1;
            } else {                、
            //或者写成else if (nums[mid] < nums[r]) 因为l<r,mid始终小于r。所以不存在==的情况
                r = mid;
            }
        }        
        return nums[l];
    }
}

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

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

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

算法的时间复杂度应该为 O(log (m+n)) 。

解法：假设我们要找第 k 小数，我们可以每次循环排除掉 k/2 个数。这个第k个数就可以设置为中位数。

假设要找第七小的数字，k/2 = 3,分别对比两个数组中更小的那个，由于数组有序，更小的那个数组的前k/2个数字都可以丢弃，然后递归再进行判断，知道k=1的时候，返回两个数组中最小的那个数组。当k/2小于数组长度的时候，取数组的末尾的数字。

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int m = nums2.length;
        int left = (n + m + 1) / 2;
        int right = (n + m + 2) / 2;
        //left代表奇数的情况 right代表偶数的情况 
        //如果n + m是奇数假如等于3，left=right=2 如果是偶数假如等于4  left=2 right=3 刚好
        return (getK(nums1, 0, n - 1, nums2, 0, m - 1, left) + 
                getK(nums1, 0, n - 1, nums2, 0, m - 1, right)) * 0.5;
    }
    public int getK(int[] nums1, int start1, int end1, 
                    int[] nums2, int start2, int end2, int k) {
        //求出两个数组长度
        int len1 = end1 - start1 + 1;
        int len2 = end2 - start2 + 1;
        //为了让长度小的数组在前面 
        if (len1 > len2) return getK(nums2, start2, end2, nums1, start1, end1, k);
        //len1一定小于len2所以只需要判断len1就行，如果len1等于0，第k大的数一定在nums2中 直接返回即可
        if (len1 == 0) return nums2[start2 + k - 1];
        // 如果k=1  直接返回两个数组头部最小的那个值
        if (k == 1) return Math.min(nums1[start1], nums2[start2]);

        // 取前 k/2 个元素 如果k/2大于数组长度 取更小的值 也就是数组的末尾
        int i = start1 + Math.min(len1, k / 2) - 1;
        int j = start2 + Math.min(len2, k / 2) - 1;

        //如果第k/2个元素 nums2[j]更小的话 nums2数组的前k/2个元素丢弃 重新再比较 然后k的值也要更新
        if (nums1[i] > nums2[j]) {
            return getK(nums1, start1, end1, nums2, j + 1, end2, k - (j - start2 + 1));
        } else {
            return getK(nums1, i + 1, end1, nums2, start2, end2, k - (i - start1 + 1));
        }
    }
}