33. 搜索旋转排序数组

1. 题目描述
2. 题解

1. 题目描述

https://leetcode.cn/problems/search-in-rotated-sorted-array/
整数数组 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 。

示例 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

进阶：你可以设计一个时间复杂度为 O(log n) 的解决方案吗？

2. 题解
2022-05-04 AC, 二分查找
题解的写法是2边都二分, 我一开始想的就是把左边的移到右边去形成一整个有序的数组, 再二分
这个解法因为要找到旋转点, 那么最坏的情况就是最后一个是旋转点, 时间复杂度就是O(n)
O(logn)解法那就是直接和nums[0]比较, 来确定在左边还是在右边 ```php <?php /**
- Created by PhpStorm
- User: jtahstu
- Time: 2022/5/4 22:54
- Des: 33. 搜索旋转排序数组
- https://leetcode.cn/problems/search-in-rotated-sorted-array/ */

class Solution {

/**
 * @param Integer[] $nums
 * @param Integer $target
 * @return Integer
 */
function search($nums, $target)
{
    if (count($nums) == 1 && $nums[0] !== $target) {
        return -1;
    }
    $count = count($nums);
    $x = 0;
    for ($i = 1; $i < $count; $i++) {
        if ($nums[$i] < $nums[$i - 1]) {
            $x = $i;
            break;
        }
    }
    $nums = array_merge($nums, array_slice($nums, 0, $x));

// echo implode(‘, ‘, $nums) . PHP_EOL; $a = $this->binary_search($nums, $target, $x); return $a % $count;

// 这样貌似更好一些 // int ans = binary_search(nums, 0, idx, target); // if (ans != -1) return ans; // if (idx + 1 < n) ans = find(nums, idx + 1, n - 1, target); // return ans; }

function binary_search(&$nums, $target, $l)
{
    $r = count($nums) - 1;
    while ($l <= $r) {
        $mid = intval(($l + $r) / 2);
        $v = $nums[$mid];
        if ($target == $v) {
            return $mid;
        }
        if ($v > $target) {
            $r = $mid - 1;
        }
        if ($v < $target) {
            $l = $mid + 1;
        }
    }
    return -1;
}

// Java O(logn)解法 // public int search(int[] nums, int target) { // int n = nums.length; // if (n == 0) { // return -1; // } // // if (n == 1) { // return nums[0] == target ? 0 : -1; // } // int l = 0, r = n - 1; // while (l <= r) { // int mid = (l + r) / 2; // if (nums[mid] == target) { // return mid; // } // if (nums[0] <= nums[mid]) { // if (nums[0] <= target && target < nums[mid]) { // r = mid - 1; // } else { // l = mid + 1; // } // } else { // if (nums[mid] < target && target <= nums[n - 1]) { // l = mid + 1; // } else { // r = mid - 1; // } // } // } // return -1; // } }

var_dump((new Solution)->search([4, 5, 6, 7, 0, 1, 2], 0)); var_dump((new Solution)->search([4, 5, 6, 7, 0, 1, 2], 5)); var_dump((new Solution)->search([3, 5, 1], 3)); var_dump((new Solution)->search([1], 0));

/**

执行用时：8 ms, 在所有 PHP 提交中击败了84.54%的用户
内存消耗：18.8 MB, 在所有 PHP 提交中击败了86.60%的用户
通过测试用例：195 / 195 */ ```

1. 题目描述

2. 题解