当前位置：首页 > news >正文

leetcode笔记：Search in Rotated Sorted Array

news 来源：原创 2024/5/17 19:44:08

一.题目描写叙述

二.解题技巧

因为这道题出现了旋转的情况，即比第一个元素小的元素可能出如今数值的后半段或者不出现。

因此。能够考虑採用变种的二分查找，即在比較中间元素与目标之前，先比較第一个元素与目标的关系。这个时候，会出现三种情况：

1.第一个元素刚好等于目标，返回第一个元素的坐标，函数结束；
2.第一个元素大于目标。那么目标就可能存在被旋转到数组后面的情况，这个时候，还要比較与数组中间元素的关系，这个时候又会有三种情况：

a.中间元素大于第一个元素，这个时候。目标可能存在于数组的后半段中，递归调用函数，寻找目标的坐标；
b.中间元素等于目标。返回中间元素的坐标，函数结束；
c.中间元素小于第一个元素。这个时候。又能够分为两种情况进行：

    (1).中间元素小于目标元素。那么目标元素可能存在于数组的后半段中，递归调用函数，寻找目标的坐标；
    (2).中间元素大于目标元素。那么目标元素可能存在于数组的前半段中，递归调用函数。寻找目标的坐标；

3.第一个元素小于目标，这是也有三种情况须要考虑：

a.中间元素等于目标元素，返回中间元素的坐标，函数结束；
b.中间元素大于第一个元素，这个时候，也有两种情况要考虑：

    (1).中间元素大于目标，那么目标元素可能存在于数组的前半段中，递归调用函数，寻找目标的坐标；
    (2).中间元素小于目标，那么目标元素可能存在于数组的后半段中，递归调用函数，寻找目标的坐标；

c.中间元素小于第一个元素，那么目标元素可能存在于数组的前半段中，递归调用函数，寻找目标的坐标；

当然，还须要考虑数组的元素个数为0，1, 2,的情况，以及对于递归的过程中数组的起始位置坐标以及数组中元素的个数。这些才是这道题的难点所在，我也是调试了非常久才调通代码的。

三.演示样例代码

// 时间复杂度O(log n)。空间复杂度O(1)
#include <iostream>

using namespace std;

class Solution
{
public:
    int SearchRotatedSortedArray(int A[], int n, int target)
    {
        int start = 0;
        int end = n;
        int middle = start + (end - start) / 2;
        while (start != end)
        {
            if (target == A[middle])
                return middle;
            if (A[start] < A[middle])
            {
                if ((target < A[middle]) && (A[start] <= target))
                    end = middle;
                else
                    start = middle + 1;
            }
            else
            {
                if ((target > A[middle]) && (target <= A[end - 1]))
                    start = middle + 1;
                else
                    end = middle;
            }
        }
        return -1; // 在数组中找不到目标元素时返回-1
    }
};