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

问题描述

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

解决方案

该解决方案仍然适用于二进制搜索，您需要将阵列分成两部分进行检查。

在排序的数组中，您只需查看每个部分，并确定元素是否位于第一部分（我们称之为A）或第二部分（B）。由于通过排序数组的定义，分区A和B将被排序，这只需要分区边界和搜索关键字的一些简单比较。

在旋转排序的数组中，只能保证A和B之一被排序。如果元素位于被排序的部分中，则解决方案很简单：只需执行搜索，就像执行正常的二进制搜索。但是，如果您必须搜索未排序的部分，那么只需递归地在非排序部分调用您的搜索功能。

这样会导致时间复杂度 O（lg n）。

（实际上，我会认为这样的数据结构会附带一个索引以表示数组已经旋转了多少个位置。）

修改：Google上的搜索需要我到这个有些过时的（但正确的）主题在CodeGuru讨论同样的问题。为了补充我的答案，我将复制一些在那里给出的伪代码，以便它出现在我的解决方案（思路如下）：

 $（$）
如果设置的大小为1并设置[0] == item 
返回信息on set [0] 
将集合分成部分A和B 
如果A被排序并且项目在A的范围内
返回搜索（A）
如果B被排序，并且该项目在B的范围内
返回搜索（ B）
如果A未排序
返回搜索（A）
如果B未排序
返回搜索（B）
返回未找到
  

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

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.

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.

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.

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.)

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屋！