【面试】运算器-⑪搜索旋转排序数组

先存一下后面要用的字符⑪⑫⑬⑭⑮⑯⑰⑱⑲⑳

33. 搜索旋转排序数组

感谢力扣！

整数数组 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) 的算法解决此问题。

示例 1：
输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4
示例 2：
输入：nums = [4,5,6,7,0,1,2], target = 3
输出：-1
示例 3：
输入：nums = [1], target = 0
输出：-1
提示：

1 <= nums.length <= 5000
-104 <= nums[i] <= 104
nums 中的每个值都 独一无二
题目数据保证 nums 在预先未知的某个下标上进行了旋转
-104 <= target <= 104

1.题目分析

应该关键是找到旋转的下标，然后从那个下标开始进行折半查找，应该不是很难的题目，通过下标来做就好了。计划如下：

① 设计思路；

② 编写代码；

③ 运行程序；

④ 总结；

2.设计思路

首先遍历元素，找到一个元素满足a[i]>a[i+1]，记录i的下标作为第一个分段的点，然后二分循环查找，要么找到，要么计算二分的时候start和end值一致，退出循环；

3.代码编写

写的时候发现有点不对，改了一下，其实判断出中间点以后，应该二分的是a[0]，不是a[index]，写题目还是有意思的。

    public int search(int[] nums, int target) {
        int result = -1;
        int index = nums.length / 2;
        for (int i = 0; i < nums.length-1; i++) {
            if(nums[i]>nums[i+1]){
                index = i;
                break;
            }
        }
        if(nums.length ==0 || nums[0]==target) return 0;

        int start = 0;
        int end = 0;
        if (nums[0] < target) {

            start = 1;
            end = index;
        }else{
            start = index;
            end = nums.length - 1;
        }
        while(start != end){
            index = (start + end) / 2;
            if(nums[index]==target){
                result = index;
                break;
            }else if(nums[index]<target){
                start = index + 1;
                end = nums.length - 1;
            }else{
                start = 1;
                end = index - 1;
            }
        }
        return result;
    }

4.线上验证

①.出现了只有一个元素的时候漏判的问题，把end初值修改了一下；

②.出现了中间节点第一次就是0的情况，把start的初值修改了一下；

③陷入了改一过一的漩涡，重新整理了一下思路，把前面乱的思路纠正过来了，循环前我就是要找到正确的二分区间，循环内就是正常的二分查找就好了，不要乱七八糟的变量控制，二分查找的结束条件记得是start<=end；

    public int search(int[] nums, int target) {
        int result = -1;
        int index = nums.length - 1;
        boolean flag = true;
        for (int i = 0; i < nums.length-1; i++) {
            if(nums[i]>nums[i+1]){
                index = i;
                break;
            }
        }
        if(nums.length ==0 || nums[0]==target){
            return 0;
        }

        int start = 0;
        int end = 0;
        if (nums[0] < target) {

            start = nums.length>1?1:0;
            end = index;
        }else{
            start = index == 0 ? 1 : index+1;
            end = nums.length - 1;
        }


        while(start<=end){
            index = (start + end) / 2;
            if(nums[index]==target){
                result = index;
                break;
            }else if(nums[index]<target){
                start = index + 1;
            }else{
                end = index - 1;
            }
        }
        return result;
    }

结果：