leetcode二分问题

旧城等待， 2022-09-04 03:54 132阅读 0赞

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

class Solution {
        
        public int search(int[] nums, int target) {
        
        int i=0,j=nums.length-1;
        int flag=0;
        int mid=0;
        while(i<=j)
        {
        
            mid=i+(j-i)/2;
            if(target>nums[mid]){
        
                i=mid+1;
            }
            else if(target<nums[mid]){
        
                j=mid-1;
            }
            else{
        
                flag=1;
                break;
            }
        }
        if(flag==1){
        
        return mid;}
        else{
        
            return -1;
        }
        }
    }

278.第一个错误的版本  
你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。

假设你有 n 个版本 \[1, 2, …, n\]，你想找出导致之后所有版本出错的第一个错误的版本。

你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。

变形：\[\*\*\*\*\*\*\*\*\#\#\#\#\#\#\#\#\] 就像这样的有序数组，找第一个 \# 号.

public class Solution extends VersionControl {
        
        public int firstBadVersion(int n) {
        
        int i=1,j=n;
        int mid=1;
        while(i<j)
        {
        
            mid=i+(j-i)/2;
            if(isBadVersion(mid)==false){
        
                i=mid+1;       
            }
            else if(isBadVersion(mid)==true){
        
                j=mid;
            }
        }
        return i;//
        }
    }

和普通二分法的区别，此类找第一个出现的符号问题，每次移动一个直到两端相等，mid=i+(j-i)/2写法防止溢出。

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

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 \[-1, -1\]。

输入：nums = \[5,7,7,8,8,10\], target = 8  
输出：\[3,4\]

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

1.  搜索旋转排序数组

整数数组 nums 按升序排列，数组中的值 互不相同 。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 \[nums\[k\], nums\[k+1\], …, nums\[n-1\], nums\[0\], nums\[1\], …, nums\[k-1\]\]（下标 从 0 开始 计数）。例如， \[0,1,2,4,5,6,7\] 在下标 3 处经旋转后可能变为 \[4,5,6,7,0,1,2\] 。

给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。

输入：nums = \[4,5,6,7,0,1,2\], target = 0  
输出：4

在使用二分的前提下，数组旋转后分为两个部分，只需要将当前的num\[mid\]与num\[0\]进行比较，如果大于num\[0\]则位于左部分，否则位于右部分。

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, 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[mid] < target && target <= nums[n - 1]) {
        
                        l = mid + 1;
                    } else {
        
                        r = mid - 1;
                    }
                }
            }
            return -1;
        }
    }

1.  搜索二维矩阵

编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：

每行中的整数从左到右按升序排列。
    每行的第一个整数大于前一行的最后一个整数。

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

将二维矩阵转化成一维使用二分搜索。  
i=mid/n;j=mid%n;  
n为列数。

class Solution {
        
        public boolean searchMatrix(int[][] matrix, int target) {
        
        int m=matrix.length;
        int n=matrix[0].length;
        int left=0;int right=m*n-1;
        if(m*n==1)
    {
        
        return target==matrix[0][0];
    }    
         int falg=0;
         while(left<=right){
        
         int mid=(left+right)/2;
         int i;int j;
         i=mid/n;j=mid%n;
         if(matrix[i][j]>target){
        
             right=mid-1;
         }
         else if(matrix[i][j]<target){
        
             left=mid+1;
         }
         else{
        
         falg=1;
         break;
         }
        }
        if(falg==1)return true;
        else return false;
        }
    }

同样利用二分算法处理旋转后的数组的题目  
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 ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。

输入：nums = \[3,4,5,1,2\]  
输出：1

num\[mid\]<num\[high\]时，位于右部分，high=mid，反之位于左部分,low=mid+1;  
不能写成high=mid-1,可能会跳过最小值，例如实例中mid=1，high=mid-1就跳过了1.

class Solution {
        
        public int findMin(int[] nums) {
        
            int low = 0;
            int high = nums.length - 1;
            while (low < high) {
        
                int pivot = low + (high - low) / 2;
                if (nums[pivot] < nums[high]) {
        
                    high = pivot;//-1可能会错过最小值
                } else {
        
                    low = pivot + 1;//要么升序，要么落在最小数
                }
            }
            return nums[low];
        }
    }