在旋转排序的数组中搜索数字 [英] Searching a number in a rotated sorted Array

问题描述

给定一个可以旋转的排序数组，以最小的时间复杂度在其中找到一个元素.

Given a Sorted Array which can be rotated find an Element in it in minimum Time Complexity.

例如:数组内容可以是 [8, 1, 2, 3, 4, 5].假设您在其中搜索 8.

eg : Array contents can be [8, 1, 2, 3, 4, 5]. Assume you search 8 in it.

推荐答案

解决方案仍然适用于二分搜索，因为您需要将数组分成两部分进行检查.

The solution still works out to a binary search in the sense that you'll need to partition the array into two parts to be examined.

在排序数组中，您只需查看每个部分并确定元素是位于第一部分(我们称之为 A)还是第二部分 (B).因为，根据已排序数组的定义，分区 A 和 B 将被排序，所以这仅需要对分区边界和您的搜索键进行一些简单的比较.

In a sorted array, you just look at each part and determine whether the element lives in the first part (let's call this A) or the second part (B). Since, by the definition of a sorted array, partitions A and B will be sorted, this requires no more than some simple comparisons of the partition bounds and your search key.

在旋转排序的数组中，只能保证A和B中的一个被排序.如果元素位于已排序的部分内，则解决方案很简单:只需执行搜索，就好像您正在执行普通的二分搜索一样.但是，如果您必须搜索未排序的部分，则只需对未排序的部分递归调用搜索函数即可.

In a rotated sorted array, only one of A and B can be guaranteed to be sorted. If the element lies within a part which is sorted, then the solution is simple: just perform the search as if you were doing a normal binary search. If, however, you must search an unsorted part, then just recursively call your search function on the non-sorted part.

这最终导致 O(lg n) 的时间复杂度.

This ends up giving on a time complexity of O(lg n).

(实际上，我认为这样的数据结构会有一个伴随它的索引来指示数组已经旋转了多少个位置.)

(Realistically, I would think that such a data structure would have a index accompanying it to indicate how many positions the array has been rotated.)

编辑:在 Google 上的搜索将我带到 CodeGuru 上讨论同一问题的这个 有点过时(但正确)的主题.为了补充我的答案，我将复制那里给出的一些伪代码，以便它与我的解决方案一起出现在此处(想法遵循相同的行):

Edit: A search on Google takes me to this somewhat dated (but correct) topic on CodeGuru discussing the same problem. To add to my answer, I will copy some pseudocode that was given there so that it appears here with my solution (the thinking follows the same lines):

Search(set):
    if size of set is 1 and set[0] == item 
        return info on set[0]
    divide the set into parts A and B
    if A is sorted and the item is in the A's range
        return Search(A)
    if B is sorted and the item is in the B's range
        return Search(B)
    if A is not sorted
        return Search(A)
    if B is not sorted
        return Search(B)
    return "not found"

这篇关于在旋转排序的数组中搜索数字的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！