算法题：33. 搜索旋转排序数组（二分法）

1、算法思路

题目要求必须设计一个时间复杂度为 O(log n) 的算法解决此问题，所以我们可以采用二分法。

Step1. 先把 nums[0] 作为目标值，通过二分法找到旋转点索引；

Step2. 如果旋转点索引为0，则数组本身就是升序的，否则思想上可以将数组一分为二，看做两个升序数组。

Step3. 判断 target 目标值在一分为二后的数组的哪一个里面，从而确定左右端索引。（特殊情况：如果旋转点索引为0，则左右端索引就是 0 和 nums.length - 1）

Step4. 确认了左右端索引之后，通过二分法查找到 target 值所在索引，若不存在则返回 -1。

2、Java代码实现

public class Search {public static void main(String[] args) {Solution sol = new Solution();System.out.println(sol.search(new int[]{4,5,6,7,0,1,2}, 0));//4System.out.println(sol.search(new int[]{4,5,6,7,0,1,2}, 5));//1System.out.println(sol.search(new int[]{1,3,5,7,9}, 3));//1System.out.println(sol.search(new int[]{1,3}, 3));//1System.out.println(sol.search(new int[]{3,1}, 1));//1System.out.println(sol.search(new int[]{8,9,2,3,4}, 9));//1System.out.println(sol.search(new int[]{4,5,6,7,0,1,2}, 3));//-1System.out.println(sol.search(new int[]{1}, 0));//-1System.out.println(sol.search(new int[]{1,3}, 0));//-1}
}// 逐一查找法
//class Solution {
//    public int search(int[] nums, int target) {
//        for (int i = 0; i < nums.length; i++) {
//            if(nums[i] == target){
//                return i;
//            }
//        }
//        return -1;
//    }
//}// 二分查找法
class Solution {public int search(int[] nums, int target) {if (nums.length == 1){return nums[0] == target ? 0: -1;}// 寻找旋转点的索引int l = 1;int r = nums.length - 1;while(l <= r){int mid = l + r >> 1;if(nums[mid] > nums[0]) l = ++mid;else r = --mid;}if(l > nums.length - 1){  //旋转点为0时，数组依旧是升序排列的l = 0;r = nums.length - 1;}else if (target >= nums[0]){r = l - 1;l = 0;}else if(target <= nums[nums.length - 1]){r = nums.length - 1;}else return -1;  //target小于nums[0]又大于nums[n-1]时直接返回-1//target等于两边时直接返回索引if (nums[l] == target) return l;if (nums[r] == target) return r;// 最后进行二分查找while(l < r){int mid = l + r >> 1;if(nums[mid] == target) return mid;if(nums[mid] < target) l = ++mid;else r = --mid;}if(nums[l] != target) return -1;return l;}
}

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

示例 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
• -10^4 <= nums[i] <= 10^4
• nums 中的每个值都 独一无二
• 题目数据保证 nums 在预先未知的某个下标上进行了旋转
• -10^4 <= target <= 10^4