练习题2

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

思路

直观的思路肯定是从前往后遍历一遍。用两个变量记录第一次和最后一次遇见 target 的下标，但这个方法的时间复杂度为 O(n)，没有利用到数组升序排列的条件。由于数组已经排序，因此整个数组是单调递增的，我们可以利用二分法来加速查找的过程。

考虑 target 开始和结束位置，其实我们要找的就是数组中「第一个等于 target 的位置」（记为 left）和「第一个大于 target 的位置减一」（记为 right）。

二分查找中，寻找 left 即为在数组中寻找第一个等于 target 的下标，寻找 right 即为在数组中寻找第一个大于 target 的下标，然后将下标减一。两者的判断条件不同，为了代码的复用，我们定义 searchRange(nums,target) 表示在 nums数组中二分查找 target 的位置 。

最后，因为 target可能不存在数组中，因此我们需要重新校验我们得到的两个下标 left 和 right，看是否符合条件，不符合就返回 -1,-1。

public class 查找下标 {    public int[] searchRange(int[] nums, int target){        int len = nums.length;        if(len == 0){            return new int[]{-1,-1};        }        int firstPosition = findFirstPosition(nums,target);        if(firstPosition == -1){            return new int[]{-1,-1};        }        int lastPositon = findLastPosition(nums,target);        return new int[]{firstPosition,lastPositon};    }    private int findFirstPosition(int[] nums, int target){        int left = 0;        int right = nums.length-1;        while(left < right){ //这里没有包含left=right的情况            int mid = (left+right)/2;            if(nums[mid] < target){                //在[mid+1,right]之间找                left = mid+1;            }else if(nums[mid] > target){                //在[ledt,mid-1]之间找                right = mid-1;            }else{                //在[left,mid]之间找                right = mid;            }        }        if(nums[left] == target){            return left;        }        return -1;    }    private int findLastPosition(int[] nums, int target){        int left = 0;        int right = nums.length-1;        while(left < right){ //这里没有包含left=right的情况            int mid = (left+right+1)/2;            if(nums[mid] < target){                //在[mid+1,right]之间找                left = mid+1;            }else if(nums[mid] > target){                //在[ledt,mid-1]之间找                right = mid-1;            }else{                //在[mid，right]之间找                left = mid;            }        }        return left;    }}

• >>表示右移，如果该数为正，则高位补0，若为负数，则高位补1；
• >>>表示无符号右移，也叫逻辑右移，即若该数为正，则高位补0，而若该数为负数，则右移后高位同样补0。
• 时间复杂度：O（log n）

练习题3

整数数组 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 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

思路

这道题中，数组本身不是有序的，进行旋转后只保证了数组的局部是有序的，这还能进行二分查找吗？答案是可以的。可以发现的是，我们将数组从中间分开成左右两部分的时候，一定有一部分的数组是有序的。拿示例来看，我们从 6 这个位置分开以后数组变成了 [4, 5, 6] 和 [7, 0, 1, 2] 两个部分，其中左边 [4, 5, 6] 这个部分的数组是有序的，其他也是如此。这启示我们可以在常规二分查找的时候查看当前 mid 为分割位置分割出来的两个部分 [l, mid] 和 [mid + 1, r] 哪个部分是有序的，并根据有序的那个部分确定我们该如何改变二分查找的上下界，因为我们能够根据有序的那部分判断出 target 在不在这个部分：

• 如果 [l, mid - 1] 是有序数组，且 target 的大小满足[nums[l],nums[mid]，则我们应该将搜索范围缩小至 [l, mid - 1]，否则在 [mid + 1, r] 中寻找。

• 如果 [mid, r] 是有序数组，且 target 的大小满足 [nums[mid+1],nums[r]]，则我们应该将搜索范围缩小至 [mid + 1, r]，否则在 [l, mid - 1] 中寻找。

需要注意的是，二分的写法有很多种，所以在判断 target 大小与有序部分的关系的时候可能会出现细节上的差别。

public class 螺旋数组 {    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;    }}

复杂度分析

• 时间复杂度： O(log⁡n)，其中 n 为nums 数组的大小。整个算法时间复杂度即为二分查找的时间复杂度 O(logn)。

• 空间复杂度： O(1) 。我们只需要常数级别的空间存放变量。

2. 浮点数二分

浮点数二分：将整数二分中的mid的类型替换成double，将区间更新操作改为l=mid或r=mid，当区间长度足够小（能求出答案时），就可以结束二分。注：浮点数二分不存在边界问题。

代码示例

double binarySearch(int[] nums,int target){// eps 表示精度，取决于题目对精度的要求    double l = 0; double r = nums.length-1;    const double eps = 1e-6; //科学计数法1*10^-6 当区间长度小于eps时退出循环     while (r - l > eps){ //当区间长度大于eps时继续二分        double mid = (l + r) / 2;        if (nums[mid] > target ) r = mid;        else l = mid;    }    return l; //最后while循环退出的时候l和r近似相等}

总结

这里对文章进行总结：
        以上就是整理的二分算法的内容，本文仅仅简单介绍了二分算法，而要在具体的题目中真正掌握运用二分算法，还需要多加练习二分算法的各种题目。

来源地址：https://blog.csdn.net/lll123789456hhh/article/details/128070117