【LeetCode】33. 搜索旋转排序数组

[WGrape]

1、介绍

一个反转前的有序数组[1, 3, 4, 5, 8, 9]，反转后为[8, 9, 1, 3, 4, 5]，现在请搜索一个元素在反转后数组中的下标，不存在则返回-1。要求时间复杂度为O(logn)

题目链接 ：https://leetcode-cn.com/problems/search-in-rotated-sorted-array/

示例

输入 ：[8, 9, 1, 3, 4, 5] ，1
输出 ：2

输入 ：[8, 9, 1, 3, 4, 5] ，6
输出 ：-1

2、思路

(1) 暴力循环

最简单的方法是循环整个数组判断，时间复杂度为O(N)

(2) 找出两个单调递增的数组

从这一个数组中，找到两个单调递增的数组，然后对这两个数组做二分查找。最坏情况下，时间复杂度也是O(N)

(3) 直接二分查找

在以往的二分查找中，都是对有序的数组，那么对这种数组也会有效吗。答案是可以的，只不过需要先找到单调区间，并判断target是否可能在这个区间内

3、解题

class Solution {

    /**
     * @param Integer[] $nums
     * @param Integer $target
     * @return Integer
     */
    function search($nums, $target) {
        $left = 0;
        $right = count($nums)-1;
        
        while($left <= $right){
            $mid = intval(($left + $right)/2);
            if($nums[$mid] == $target){
                return $mid;
            }
            
            // left 到 mid 区间单调递增
            if($nums[$left] <= $nums[$mid]){
                
                // 必须同时判断 target 在 left 和 mid 之间
                if($nums[$left] <= $target && $target <= $nums[$mid]){
                    $right = $mid - 1;
                }
                
                else{
                    $left = $mid +1 ;
                }
            }
            
            // mid 到 right 区间单调递增
            else{

                // 必须同时判断 target 在 mid 和 right 之间
                if($nums[$mid] <= $target && $target <= $nums[$right]){
                    $left = $mid + 1;
                }
                
                else{
                    $right = $mid - 1;
                }
            }
        }
        
        return -1;
    }
}