搜索旋转排序数组

怼烎@ 2023-10-04 20:41 59阅读 0赞

## 搜索旋转排序数组 ##

### **1.1题目描述** ###

力扣的第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.2解题** ###

用二分查找就可以，只不过与常规的二分查找相比，有更复杂的判断条件。如下图，假如target介于left和mid之间，那么会有下面三种可能，所以只要把三种情况的条件找准确，那么就变成基本的二分查找了。基本的二分查找可以参考[https://blog.csdn.net/u013978512/article/details/121174357?spm=1001.2014.3001.5501][https_blog.csdn.net_u013978512_article_details_121174357_spm_1001.2014.3001.5501]，该文章的方式可以避免二分查找的很多易错的细节。

![296e6a2401f1909953a8b9a4973cdb5b.png][]

代码如下：

public int search(int[] nums, int target) {
            int head = nums[0];
            int left = -1;
            int right = nums.length;
            int mid = 0;
            while(left + 1 != right) {
                mid = (left + right) / 2;
                if(nums[mid] == target) {
                    return mid;
                } else if ((target < nums[mid] && target >= head)
                        || (nums[mid] < head && (target >= head || target < nums[mid]))) {
                    right = mid;
                } else {
                    left = mid;
                }
            }
            if(right >= nums.length || target != nums[right]) {
                return -1;
            }
            return right;
        }

战果如下：

![2d89a0de3d47831eea08daafda7f785f.png][]

[https_blog.csdn.net_u013978512_article_details_121174357_spm_1001.2014.3001.5501]: https://blog.csdn.net/u013978512/article/details/121174357?spm=1001.2014.3001.5501
[296e6a2401f1909953a8b9a4973cdb5b.png]: https://img-blog.csdnimg.cn/img_convert/296e6a2401f1909953a8b9a4973cdb5b.png
[2d89a0de3d47831eea08daafda7f785f.png]: https://img-blog.csdnimg.cn/img_convert/2d89a0de3d47831eea08daafda7f785f.png