1. 概述

假设按照升序排序的数组在预先未知的某个点上进行了旋转。 ( 例如，数组 [0,0,1,2,2,5,6] 可能变为 [2,5,6,0,0,1,2] )。

编写一个函数来判断给定的目标值是否存在于数组中。若存在返回 true，否则返回 false。

示例 1:

输入: nums = [2,5,6,0,0,1,2], target = 0

输出: true

示例 2:

输入: nums = [2,5,6,0,0,1,2], target = 3

输出: false

2. 解题

<?php
class Solution
{
    private $exchange = [
        'mid' => -1,
        'left' => -1,
        'right' => -1,
    ];
    /**
     * @param Integer[] $nums
     * @param Integer $target
     * @return Boolean
     */
    public function search($nums, $target)
    {
        $left = 0;
        $right = count($nums) - 1;
        // 二分法，先检查正确排序的一边，再找乱序一边（乱序先找左，再找右）
        while (!$ret = $this->do($nums, $target, $left, $right)) {
            $mid = $this->exchange['mid'];
            if ($mid == -1 || 0 > $mid || $mid > count($nums) - 1) {
                break;
            }
            $this->exchange['mid'] = -1;
            $left = $mid + 1;
            $right = $this->exchange['right'];
        }
        return $ret;
    }
    /**
     * @param array $nums
     * @param int $target
     * @param int $left
     * @param int $right
     * @return bool
     */
    private function do(array $nums, int $target, int $left, int $right)
    {
        while ($left <= $right) {
            $mid = $left + floor(($right - $left) / 2);
            if ($nums[$mid] == $target) {
                echo "key: " . $mid . "\n";
                return true;
            } elseif ($nums[$left] < $nums[$mid]) {         // 左升序
                if ($nums[$left] <= $target && $target < $nums[$mid]) {
                    $right = $mid - 1;
                } else {
                    $left = $mid + 1;
                }
            } elseif ($nums[$mid] < $nums[$right]) {        // 右升序
                if ($nums[$mid] <= $target && $target < $nums[$right]) {
                    $left = $mid + 1;
                } else {
                    $right = $mid - 1;
                }
            } else {                                        // 逆序
                if ($this->exchange['mid'] == -1) {
                    $this->exchange['mid'] = $mid;
                    $this->exchange['left'] = $left;
                    $this->exchange['right'] = $right;
                }
                if ($nums[$mid] == $nums[$left]) {
                    $right--;
                } else {
                    $left++;
                }
            }
        }
        return false;
    }
}
$nums = [2,5,6,0,0,1,2];
// $nums = [2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 2];
$target = 1;
$cls = new Solution();
$ret = $cls->search($nums, $target);
var_dump($ret);