33. Search in Rotated Sorted Array

Tags

1. Array
2. Binary Search

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

题意：

假设一个按升序排序的数组在预先未知的某个旋转轴上旋转。 （即0 1 2 4 5 6 7 可能变为 4 5 6 7 0 1 2）。 给你一个搜索的目标值。如果在返回的数组索引，否则返回-1。 你可以假设没有重复的数在数组中存在。

分析：

一看到题意就打算使用折半查找法，不过题目中说升序数组可能中途折断，不是一直升序的，因此我们在折半查找时需要多做一些条件判断。具体详见代码。

思路：

折半查找法

复杂度：

时间复杂度O(log(n));

Js实现：

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function(nums, target) {
    let lo = 0;
    let hi = nums.length - 1;
    while (lo < hi) {
        let mid = Math.floor((lo + hi) / 2);
        if (nums[mid] == target) return mid;

        // 升序
        if (nums[lo] <= nums[mid]) {
            //目标值大于最小位的值且小于中位值
            if (target >= nums[lo] && target < nums[mid]) {
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
        } else {
        // 折断位置
        //目标值大于中位值且小于最后位置值
            if (target > nums[mid] && target <= nums[hi]) {
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
    }
    return nums[lo] == target ? lo : -1;
};