0

我需要在排序和旋转的数组中搜索一个元素（数组可能包含重复的元素）。排序和旋转数组意味着排序数组旋转了 k 个元素。

int sortedpivot( int arr[], int start , int end , int x)
{
        if ( start > end ) return -1;

        if ( start == end ) return x== arr[start]? start : -1;

        int mid = ( end - start ) /2 + start ;
        if ( arr[ mid] == x) return mid;

        if ( arr[ mid] > arr[ start])
        {
                if (    x< arr[ mid] && x>= arr[ start])
                        return sortedpivot( arr, start , mid-1, x);
                else
                        return sortedpivot( arr, mid + 1, end , x);

        }

        else
        {
                if (    x> arr[ mid] && x<= arr[ end])
                        return sortedpivot( arr, mid+1, end, x);
                else
                        return sortedpivot( arr, start, mid-1 , x);

        }


}

上面的代码在包含重复元素的数组中失败。任何人都可以提出改进建议吗？

4

2 回答 2

0

下面的python代码执行数组的旋转并使用二进制搜索搜索元素

import random


def rotate(a):
    n = len(a)
    tmp = a[n-1]
    for i in range(N-2,-1, -1):
        a[i+1]=a[i]
    a[0] = tmp

def rotate_multi(a,t):
    if t > len(a):
         return
    for i in range(t):
        rotate(a)


def binary_search(a,l,h,item):
    if l > h:
        return -1

    m = (l+h)//2
    if a[m] == item:
        return m
    elif a[m] > item:
        return binary_search(a,l,m-1,item)
    else:
        return binary_search(a,m+1,h,item)    


def find(a,item):
    pos = 0
    for i in range(len(a)-1):
        if a[i] > a[i+1]:
            pos = i
            break
    if a[pos] == item:
        return pos
    elif item > a[len(a)-1]:
        return binary_search(a,0,pos,item)
    else:
        return binary_search(a,pos+1,len(a)-1,item)


if __name__=="__main__":
    print("Python program for Array rotation and binary search")
    N = int(input("How many numbers?"))
    a = random.sample(range(1,1000), N)
    print("The input numbers are")
    a.sort()
    print(a)
    r = random.randint(1,N)
    rotate_multi(a,r)
    print("The input numbers after %d rototations" %r)
    print(a)
    item= int(input("Enter the number to search ?"))
    pos = find(a,item)
    if pos == -1:
        print("The number %d not found in the array " %item)
    else:
        print("The number %d found at the position in the array at postition %d" %(item, pos+1))

输出：

用于数组旋转和二进制搜索的 Python 程序

多少个数字？10

输入数字是

[108、351、426、492、551、563、617、687、720、780]

7 次旋转后的输入数字

[492、551、563、617、687、720、780、108、351、426]

输入号码搜索?720

在数组中位置 6 的位置找到数字 720

于 2018-04-04T15:01:28.187 回答
0

一个可能的答案可能是..

1）首先找到最小元素并使其按排序顺序排列。

         Complexity : worst-case O(n)

2) 通过二分搜索搜索所需元素。

         Complexity : log(n)
于 2016-09-23T18:02:33.207 回答