在旋转的排序数组中搜索数字

Question

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

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

Answer 1

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

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

在旋转的有序数组中,只能保证对A和B中的一个进行排序.如果元素位于已排序的部分内,则解决方案很简单:只需执行搜索,就像进行常规二进制搜索一样.但是,如果必须搜索未排序的部分,则只需在未排序的部分上递归调用搜索功能.

这最终给出了时间的复杂性O(lg n).

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

编辑:在Google上搜索带我到CodeGuru讨论相同问题的这个有点过时(但正确)的主题.为了添加我的答案,我将复制一些在那里给出的伪代码,以便它出现在我的解决方案中(思路遵循相同的路线):

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"

Answer 2

为O(log(N))

减少到找到最大数字位置的问题,这可以通过检查区域的第一个和最后一个和中间数来完成,递归地减少区域,划分和征服,这是O(log(N))不大于二分搜索O(log(N)).

编辑:例如,你有

6 7 8 1 2 3 4 5  
^       ^     ^ 

通过查看3个数字,您知道最小/最大数字的位置(稍后将被称为标记)位于6 7 8 1 2的范围内,因此不考虑3 4 5(通常通过移动您的区域来完成)开始/结束索引(int)指向数字6和2).

下一步,

6 7 8 1 2  
^   ^   ^  

再次,您将获得足够的信息来判断标记的哪一侧(左侧或右侧),然后该区域再次减少一半(至6 7 8).

这个想法是:我认为你可以改进一个更好的版本,实际上,对于一次采访,一个干净的代码的OK算法比使用OK代码的最佳算法更好:你最好亲自动手一些升温.

祝好运!

Answer 3

我最近在一次采访中被问到这个问题.问题是描述了一个搜索循环排序数组中"密钥"的算法.我也被要求编写相同的代码.这就是我想出的:

使用分而治之二进制搜索.对于每个子数组,检查数组是否已排序.如果排序使用经典二进制搜索,例如

data [start] <data [end]表示数据已排序.用户二进制else将数组进一步分割,直到我们得到排序数组.

    public boolean search(int start,int end){
    int mid =(start+end)/2;
    if(start>end)
    {
        return  false;
    }
    if(data[start]<data[end]){
        return this.normalBinarySearch(start, end);
    }
    else{
        //the other part is unsorted.
        return (this.search(start,mid) ||
        this.search(mid+1,end));
    }
}

其中normalBinarySearch是一个简单的二进制搜索.

Answer 4

它是普通二进制搜索的简单修改.事实上,我们它将适用于旋转和排序的数组.在排序数组的情况下,它最终将完成比实际需要更多的工作.

对于旋转数组,当您将数组拆分为两个子数组时,其中一个子数组可能不会按顺序排列.您可以通过比较子阵列中的第一个和最后一个值来轻松检查是否每个半部分都已排序.

知道每个子阵列是否已排序,我们可以选择下一步做什么.

1)对左子阵列进行排序,并且该值在左子阵列的范围内(检查两端!)

然后搜索递归搜索左子阵列.

2)对右子阵列进行排序,并且该值在右子阵列的范围内(检查两端!)

然后递归搜索右子阵列.

3)左边没有排序

然后递归搜索左子阵列

4)权利没有排序

然后递归搜索右子阵列.

注意:这与普通二进制搜索之间的区别在于,我们不能简单地通过简单地比较左子阵列的最后一个值(右子阵列的第一个值)来做出我们的决定.该值必须严格地在左或右子阵列中,并且该子阵列必须排序,否则我们必须递归到未排序的子阵列.

以下是一些实现此目的的Objective-C:

@implementation BinarySearcher

- (BOOL)isValue:(int)value inArray:(int[])array withArraySize:(int)size {

    return [self subSearchArray:array forValue:value fromIndex:0 toIndex:size -1];
}

- (BOOL)subSearchArray:(int[])array forValue:(int)value fromIndex:(int)left toIndex:(int)right {

    if (left <= right) {

        int middle = (left + right) / 2;

        BOOL leftArraySorted = array[left] <= array[middle];
        BOOL rightArraySorted = array[middle + 1] <= array[right];

        if (array[middle] == value) {
            return YES;
        } else if (leftArraySorted && value >= array[left] && value < array[middle]) {
            return [self subSearchArray:array forValue:value fromIndex:left toIndex:middle];
        } else if (rightArraySorted && value >= array[middle + 1] && value <= array[right]) {
            return [self subSearchArray:array forValue:value fromIndex:middle + 1 toIndex:right];
        } else if (!leftArraySorted) {
            return [self subSearchArray:array forValue:value fromIndex:left toIndex:middle];
        } else if (!rightArraySorted) {
            return [self subSearchArray:array forValue:value fromIndex:middle + 1 toIndex:right];
        }
    }

    return NO;
}

@end