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

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.

数组内容可以是[8、1、2、3、4、5]。假设你在其中搜索了8。

21 个解决方案

#1

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.

排序数组,你看看每个部分和确定元素住在第一部分(我们称之为)或(B)。第二部分,通过排序数组的定义,将分类分区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.

在旋转排序的数组中，只有一个a和B可以保证被排序。如果元素位于已排序的部分中，那么解决方案很简单:只需执行搜索，就像执行普通的二分查找一样。但是，如果您必须搜索未排序的部分，那么只需递归地调用未排序部分的搜索函数。

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

这最终给出了O(lgn)的时间复杂度。

(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):

编辑:在谷歌上的搜索把我带到了这个有点过时(但正确)的主题上，关于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"

#2

O(log(N))

O(log(N))

Reduced to the problem of finding the largest number position, which can be done by checking the first and last and middle number of the area, recursively reduce the area, divide and conquer, This is O(log(N)) no larger than the binary search O(log(N)).

通过检查该区域的第一个和最后一个和中间的数，再递归地减少面积，分治和征服，这就是O(log(N))不大于二分查找O(log(N))。

EDIT: For example, you have

编辑:例如，你有。

6 7 8 1 2 3 4 5  
^       ^     ^ 

By looking at the 3 numbers you know the location of the smallest/largest numbers (will be called mark later on) is in the area of 6 7 8 1 2, so 3 4 5 is out of consideration (usually done by moving your area start/end index(int) pointing to the number 6 and 2 ).

通过观察3号你知道最小/最大数字的位置(稍后将被称为马克)是在6 7 8 1 2的面积,所以3 4 5的考虑(通常是通过移动你的区域开始/结束索引(int)指向数字6和2)。

Next step,

下一步,

6 7 8 1 2  
^   ^   ^  

Once again you will get enough information to tell which side (left or right) the mark is, then the area is reduced to half again (to 6 7 8).

再一次，你将得到足够的信息来判断哪边(左或右)的标记，然后面积又减少到一半(到6 7 8)。

This is the idea: I think you can refine a better version of this, actually, for an interview, an OK algorithm with a clean piece of codes are better than the best algorithm with OK codes: you 'd better hand-on some to heat-up.

这个想法是这样的:我认为你可以改进一个更好的版本，实际上，对于一个面试来说，一个好的算法和一个干净的代码比最好的算法更好的代码:你最好的手一些来加热。

Good luck!

好运！

#3

I was asked this question in an interview recently.The question was describe an algorithm to search a "key" in a circular sorted array.I was also asked to write the code for the same. This is what I came up with:

最近我在一次面试中被问到这个问题。问题是描述一个算法在一个循环排序的数组中搜索“键”。我也被要求写同样的代码。这就是我想到的:

Use divide and conquer binary search. For each subarray check if the array is sorted. If sorted use classic binary search e.g

使用分割和征服二分查找。对于每个子数组，检查数组是否被排序。如果分类使用经典的二分查找。

data[start]< data[end] implies that the data is sorted. user binary else divide the array further till we get sorted array.

数据[开始] <数据[端]意味着数据被排序。用户二进制文件进一步划分数组，直到我们得到排序的数组。< p>

    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));
    }
}

where normalBinarySearch is a simple binary search.

在这里，normalBinarySearch是一个简单的二分查找。

#4

It a simple modification of normal binary search. In fact we it will work for both rotated and sorted arrays. In the case of sorted arrays it will end up doing more work than it really needs to however.

它是对普通二分查找的简单修改。实际上，它将对旋转和排序的数组都有效。在排序数组的情况下，它最终会完成比实际需要更多的工作。

For a rotated array, when you split the array into two subarrays, it is possible one of those subarrays will not be in order. You can easily check if if each half is sorted by comparing the first and last value in the subarray.

对于一个旋转的数组，当将数组拆分为两个子数组时，其中的一个子数组是不可能的。通过比较子数组中的第一个值和最后一个值，您可以轻松地检查是否对每个部分进行排序。

Knowing whether each subarray is sorted or not, we can make a choice of what do do next.

知道每个子数组是否已排序，我们可以选择下一步做什么。

1) left subarray is sorted, and the value is within the range of the left subarray (check both ends!)

1)左子数组已排序，值在左子数组的范围内(检查两端!)

Then search recursively search left subarray.

然后搜索递归搜索左子数组。

2) right subarray is sorted, and the value is within the range of the right subarray (check both ends!)

2)正确的子数组被排序，值在右子数组的范围内(检查两端!)

Then recursively search right subarray.

然后递归搜索右子数组。

3) left is Not sorted

3)左边没有排序。

Then recursively search left subarray

然后递归搜索左子数组。

4) Right is Not sorted

4)对不对。

Then recursively search right subarray.

然后递归搜索右子数组。

Note: the difference between this and a normal binary search is that we cannot simply choose the subarray to recurse on by simply comparing the last value left subarray (of first value of the right subarray) to make our decision. The value has to be strictly in the left or right subarray and that subarray has to sorted, otherwise we must recurse on the unsorted subarray.

注意:这与普通的二分查找的区别在于，我们不能简单地通过比较最后一个值左子数组(右子数组的第一个值)来选择递归的子数组来做出我们的决定。值必须严格地在左或右子数组中，子数组必须进行排序，否则我们必须递归到未排序的子数组中。

Here is some Objective-C that implements this:

这里是一些实现这个的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

#5

At any index, one partition will be sorted and other unsorted. If key lies within sorted partition, search within sorted array, else in non sorted partition.

在任何索引中，一个分区将被排序，而另一个分区则是未排序的。如果键位于已排序的分区内，则在有序数组中搜索，否则在非排序分区中搜索。

BS(lo, hi)
m = (lo + hi)/2
if(k = a[m])
    return m
b = 0
if(a[hi] > a[m])
    b = 1
if(b)
    if(k > a[m] && k<a[hi])
        BS(m+1, hi)
else
    BS(lo, m-1)

#6

Here is my approach at it:

下面是我的方法:

public static int findMin(int[] a, int start, int end){
  int mid = (start + end)/2;
  if(start == mid){
    return a[mid+1];
  }else if(a[start] > a[mid]){
    return findMin(a, start, mid);
  }else if(a[mid+1] > a[start]){
    return findMin(a, mid+1, end);
  }else{
    return a[mid+1];
  }
}

Time complexity: O(log n)

时间复杂度:O(log n)

#7

You can wrap an array with a class that only exposes

您可以用只公开的类包装数组。

E get(int index);

E(int指数);

and would behave as regular sorted array. For ex if you have 4 5 1 2 3 4, wrapper.get(0) will return 1.

它会表现为有序数组。对于ex，如果你有4 5 1 2 3 4,wrapper.get(0)将返回1。

Now you can just reuse binary search solution.

现在你可以重新使用二进制搜索解决方案。

Wrapper can look like that:

包装器可以是这样的:

class RotatedArrayWrapper<T> {
  int startIndex;
  private final List<T> rotatedArray;

  public RotatedArrayWrapper(List<T> rotatedArray) {
    this.rotatedArray = rotatedArray;
    //find index of the smalest element in array
    //keep in mind that there might be duplicates
    startIndex = ... 
  } 

  public T get(int index) {
    int size = rotatedArray.size();
    if (index > size) throw Exception...

    int actualIndex = (startIndex + index) % size;
    return rotatedArray.get(actualIndex);
  }
}

#8

Python implementation. Could use to be more pythonic:

Python实现。可以用更多的python语言:

from bisect import bisect_left


def index(a, x):
    """Binary search to locate the leftmost value exactly equal to x.
    see http://docs.python.org/2/library/bisect.html#searching-sorted-lists

    >>> index([5, 14, 27, 40, 51, 70], 27)
    2
    >>> index([1, 2, 3, 4], 10)
    Traceback (most recent call last):
        ...
    ValueError
    """
    i = bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    raise ValueError


def _index_shifted(value, sequence, start, stop):
    """Recursive reset location and binary search"""
    # if at reset (min) and it's not the value, it's not there
    if start == stop and sequence[start] != value:
        return -1
    mid = (stop + start) // 2
    # check mid, since we are already here
    if sequence[mid] == value:
        return mid
    # right side is sorted
    elif sequence[mid] < sequence[stop]:
        # if value falls in range, search righ
        if sequence[stop] >= value > sequence[mid]:
            return index(sequence[mid:stop + 1], value) + mid
        # partition left side
        return _index_shifted(value, sequence, start, mid)
    # left side is sorted
    else:
        # if value falls in range, search left
        if sequence[mid] > value >= sequence[start]:
            return index(sequence[start:mid], value) + start
        # partition right side
        return _index_shifted(value, sequence, mid + 1, stop)


def index_shifted(sequence, value):
    """Returns index of value in a shifted sorted sequence; -1 if not present.

    >>> index_shifted([10, 13, 16, 19, 22, 25, 28, 31, 34, 37], 10)
    0
    >>> index_shifted([10, 13, 16, 19, 22, 25, 28, 31, 34, 37], 37)
    9
    >>> index_shifted([34, 37, 10, 13, 16, 19, 22, 25, 28, 31], 10)
    2
    >>> index_shifted([34, 37, 10, 13, 16, 19, 22, 25, 28, 31], 37)
    1
    >>> index_shifted([34, 37, 10, 13, 16, 19, 22, 25, 28, 31], 13)
    3
    >>> index_shifted([34, 37, 10, 13, 16, 19, 22, 25, 28, 31], 25)
    7
    >>> index_shifted([25, 28, 31, 34, 37, 10, 13, 16, 19, 22], 10)
    5
    >>> index_shifted([25, 28, 31, 34, 37, 10, 13, 16, 19, 22], -10)
    -1
    >>> index_shifted([25, 28, 31, 34, 37, 10, 13, 16, 19, 22], 100)
    -1
    """
    return _index_shifted(value, sequence, 0, len(sequence) - 1)

#9

//this solution divides the array in two equal subarrays using recurssion and apply binary search on individual sorted array and it goes on dividing unsorted array

//这个解决方案将数组分成两个相等的子数组，使用递归，并对单个排序的数组进行二分查找，然后继续进行未排序的数组的划分。

public class SearchRotatedSortedArray
{
    public static void main(String... args)
    {
        int[] array={5,6,1,2,3,4};

        System.out.println(search(array,Integer.parseInt(args[0]),0,5));
    }

    public static boolean search(int[] array,int element,int start,int end)
    {   
    if(start>=end)
    {
        if (array[end]==element) return true;else return false;
    }

    int mid=(start+end)/2;
    if(array[start]<array[end])
    {
        return binarySearch(array,element,start,end);
    }

    return search(array,element,start,mid)||search(array,element,mid+1,end);    
}

    public static boolean binarySearch(int[] array,int element,int start,int end)
    {
        int mid;

        while(start<=end)
        {
            mid=(start+end)/2;

            if(array[mid]==element)
            return true;

            if(array[mid]<element)
            {
                start=mid+1;

            }
            else
            {
                end=mid-1;

            }
        }

        return false;
    }
}

#10

int findIndexInRotatedSort( vector<int> input, int s, int e, int toFind )
    {
        if (s > e || s >= input.size() || e < 0)
        {
            return -1;
        }

        int m = (s + e)/2;

        int sVal = input.at(s);
        int eVal = input.at(e);
        int mVal = input.at(m);

        if (sVal == toFind)
            return s;
        if (eVal == toFind)
            return e;
        if (mVal == toFind)
            return m;

        bool isFirstOrdered = (sVal < mVal);
        bool isSecondOrdered = (mVal < eVal);
        if (toFind > mVal)
        {
            if (!isSecondOrdered || toFind < eVal)
            {
                return findIndexInRotatedSort( input, m+1, e, toFind );
            }
            else
            {
                return findIndexInRotatedSort( input, s, m-1, toFind );
            }
        }
        else
        {
            if (!isFirstOrdered || toFind > sVal)
            {
                return findIndexInRotatedSort( input, s, m-1, toFind );
            }
            else
            {
                return findIndexInRotatedSort(  input, m+1, e, toFind );
            }
        }
    }

#11

public class RoatatedSorted {

/**
 * @param args
 */
public static void main(String[] args) {
    // TODO Auto-generated method stub

    int[] rotArray = {5,6,7,8,9,10,15,16,17,1,2,3,4,};

    search(rotArray,0,rotArray.length-1,10);

}

private static void search(int[] a, int low, int high,int key) {

    //int mid =  low + (high-low)/2;
    //if(a[mid]==a[key]){System.out.println("element found at" + key+1 +" position"); return;}

    // find pos to split array
    int pos = findSplitIndex(a,low,high);
    System.out.println("split pos found at" + pos +" position");


    if(key>=a[low]&& key <=a[pos])
        bsearch(a,low,pos,key);
    if(key>=a[pos+1]&& key <=a[high])
        bsearch(a,pos+1,high,key);  
}


private static void bsearch(int[] a, int low, int high,int key) {
    // TODO Auto-generated method stub
    if(low>high) return;
    int mid =  low + (high-low)/2;
    if(a[mid]==key)
    {System.out.println("element found at" + ++mid +" position"); return;}
    if(a[mid] > key)
        bsearch(a,low,mid-1,key);
    if(a[mid]<key)
        bsearch(a,mid+1,high,key);
}

private static int findSplitIndex(int[] a, int low, int high) {
    // TODO Auto-generated method stub
    int mid;
    if(low>high)return -1;
    while(true) {
        mid =  low + (high-low)/2;
    if( a[mid]>a[mid+1])
    break;


    if(a[mid]>a[low])
        low=mid;
    if(a[high]>a[mid])
        high=mid;
}
    return mid;


}

}

#12

First to find the Minimum element in the array then divide array in two part. After that search the given value using Binary search tree. Complexity : O(logn) If you have to find the Minimum element in the rotated Array, use same approach,just skip Binary search. Complexity : O(logn)

首先找到数组中的最小元素，然后将数组分成两部分。然后用二叉搜索树搜索给定的值。复杂度:O(logn)如果你必须找到旋转数组中最小的元素，使用相同的方法，跳过二分查找。复杂性:O(logn)

//Search an element in a sorted and pivoted array
    class SearchInPivotedSortedArray
    {
        //searchInOrtedPivotedArray : Return index of matched element with given value.
        public static int searchInSortedPivotedArray(int[] A, int value)
        {
            int min = findMinElement(A,0,A.Length-1);
            if (min == A[0])
               return binarySearchTree(A, 0, A.Length-1, value);


            if (value <= A[A.Length-1])
               return binarySearchTree(A, min, A.Length-1, value);
            else
               return binarySearchTree(A, 0, min-1, value);


        }
        //return index of Pivot element
        public static int findMinElement(int[] Array, int low, int high)
        {

            if (low >= high)
                return low;

            int mid = (low + high) / 2;
            if (mid > low && Array[mid] < Array[mid - 1])
                return mid;
            if (mid < high && Array[mid] > Array[mid + 1])
                return mid + 1;

            if (Array[mid] < Array[high])
                return findMinElement(Array, low, mid - 1);

            return findMinElement(Array, mid + 1, high);

        }
        //Return match element index, if not found return -1
        public static int binarySearchTree(int[] array, int low, int high,int value)
        {
            if (low > high)
                return -1;
            int mid = (low + high)/2;

            if (array[mid] == value)
                return mid;
            if (array[mid] > value)
                return binarySearchTree(array, low, mid - 1, value);
            else
                return binarySearchTree(array, mid + 1, high, value);

        }
    }

#13

this is a O(logn) solution: tested. it works on both sorted and rotated sorted arrays:

这是一个O(logn)解决方案:测试。它在排序和旋转的排序数组中工作:

public static int rbs(int[] a, int l, int r, int t) {

    if (a[l] <= a[r]) {
        return bs(a, l, r, t);
    }

    if (r < l) {
        return -1;
    } else {
        int m = (l+r) / 2;
        if (a[m] == t) {
            return m;
        } else if (a[m] > t) { // check left half
            if (a[l] > a[m]) { // left is unsorted
                return rbs(a, l, m-1, t);
            } else { // left is sorted
                if (a[l] < t) { // t is in range
                    return bs(a, l, m-1, t);
                } else if (a[l] > t) { // t is out of range on left
                    if (a[r] >= t) {
                        return rbs (a, m+1, r, t);
                    } else
                        return -1;
                } else
                    return l;
            }
        } else { // other side
            if (a[r] < a[m]) { // right is unsorted
                return rbs(a, m+1, r, t);
            } else { // right is sorted
                if (a[r] > t) { // t is in range
                    return bs(a, m+1, r, t);
                } else if (a[r] < t) { // t is out of range on right side
                    if (a[l] <= t) {
                        return rbs (a, l, m-1, t);
                    } else
                        return -1;
                } else
                    return r;
            }
        }
    }
}


public static int bs(int[] a, int l, int r, int t) {

    int m = (l+r) / 2;

    if (r < l) {
        return -1;
    } else {
        if (a[m] == t)
            return m;
        else if (a[m] < t)
            return bs(a, m+1, r, t);
        else
            return bs (a, l, m-1, t);
    }
}

#14

Try out this solution,

尝试这个解决方案,

     public static int findElement(int[] a, int key, int left, int right) {

           if (left > right) {
              return -1;
           }

           int mid = (left + right) / 2;

           if (key == a[mid]) {
              return mid;
           } else if (key < a[mid]) {
              return (a[left] <= a[mid] && a[left] < key ? findElement(
                a, key, left, mid - 1) : findElement(a, key,
                mid + 1, right));
           } else {
              return (a[mid] <= a[right] && a[right] < key ? findElement(
                a, key, left, mid - 1) : findElement(a, key,
                mid + 1, right));
    }

}

#15

Here is a C++ implementation of @Andrew Song's answer

这是一个c++实现的@Andrew Song的答案。

int search(int A[], int s, int e, int k) {
    if (s <= e) {
        int m = s + (e - s)/2;
        if (A[m] == k)
            return m;
        if (A[m] < A[e] && k > A[m] && k <= A[e]) 
            return search(A, m+1, e, k);
        if (A[m] > A[s] && k < A[m] && k >= A[s]) 
            return search(A, s, m-1, k);
        if (A[m] < A[s]) 
            return search(A, s, m-1, k);
        if (A[m] > A[e])
            return search(A, m+1, e, k);
    }
    return -1;
}

#16

This is 100% working and tested solution in PYTHON

这是在PYTHON中100%使用和测试的解决方案。

Program to find a number from a sorted but rotated array

程序从已排序但旋转的数组中查找一个数字。

def findNumber(a, x, start, end):
  if start > end:
    return  -1
  mid = (start + end) / 2
  if a[mid] == x:
    return mid
  ## Case : 1  if a[start] to a[mid] is sorted , then search first half of array
  if a[start] < a[mid]:
    if (x >= a[start] and x <= a[mid]):
      return findNumber(a, x, start, mid - 1)
    else:
      return findNumber(a,x, mid + 1, end)
  ## Case: 2 if a[start] to a[mid] is not sorted , then a[mid] to a[end] mist be sorted
  else:
    if (x >= a[mid] and x <= a[end]):
      return findNumber(a, x, mid + 1, end)
    else:
      return findNumber(a,x, start, mid -1)


a = [4,5,6,7,0,1,2]
print "Your array is  : " , a
x = input("Enter any number to find in array : ")
result = findNumber(a, x, 0, len(a) - 1)
print "The element is present at %d position: ", result

#17

def search(array, left, right, target): # Stop conditions for recursion. if not array: return -1 if left == right: return left if array[left] == target else -1

def搜索(数组，左，右，目标):递归的停止条件。如果不是数组:返回-1如果左边==右:如果数组[左]== =目标-1返回左。

    # Check if middle element is same as the target.
    mid = (left + right) / 2
    if array[mid] == target:
        return mid

    # Pivot point is at the right of the middle element.
    if array[left] <= array[mid]:
        if target >= array[left] and target <= array[mid]:
            return search(array, left, mid - 1, target)
        return search(array, mid + 1, right, target)

    # Pivot point is at the left of the middle element.
    if target >= array[mid] and target <= array[right]:
        return search(array, mid + 1, right, target)
    return search(array, left, mid - 1, target)

I found the solution from this post

我从这篇文章中找到了解决办法。

#18

My solution: efficiency: O(logn)

我的解决方案:效率:O(logn)

public static int SearchRotatedSortedArray(int l, int d, int[] array, int toFind) {
    if (l >= d) {
        return -1;
    }
    if (array[l] == toFind) {
        return l;
    }
    if (array[d] == toFind) {
        return d;
    }

    int mid = (l + d) / 2;
    if (array[mid] == toFind) {
        return mid;
    }

    if ((array[mid] > toFind && toFind > array[l]) || (array[mid] < toFind && array[d] < toFind)) {
        return SearchRotatedSortedArray(l, mid - 1, array, toFind);
    } else {
        return SearchRotatedSortedArray(mid + 1, d, array, toFind);
    }

}

#19

In worst case you have to use linear search and examine whole array to find a target, because, unlike a set, an array may contain duplicates. And if an array contains duplicates you can't use binary search in the given problem.

在最坏的情况下，您必须使用线性搜索并检查整个数组以查找目标，因为与set不同，数组可能包含重复项。如果一个数组包含重复项，则在给定的问题中不能使用二进制搜索。

If queries on particular array are infrequent you can use standard binary search if whole array is sorted (first element is strictly smaller than last element) and use linear search otherwise. For more information see How fast can you make linear search? discussion on * and 10 Optimizations on Linear Search article by Thomas A. Limoncelli.

如果对特定数组的查询不频繁，则可以使用标准的二进制搜索，如果整个数组是排序的(第一个元素严格小于最后一个元素)，则可以使用线性搜索。要了解更多信息，请查看如何快速进行线性搜索?关于*的讨论和Thomas A. Limoncelli关于线性搜索的10个优化。

Hovewer, if queries are frequent you can sort input array in linear time (see Fastest algorithm for circle shift N sized array for M position discussion on *) in preprocessing step and use standard binary search as usual.

Hovewer，如果查询频繁的话，您可以在线性时间内对输入数组进行排序(请参阅在预处理步骤中对*上的M位置讨论的最快速算法)，并像往常一样使用标准的二进制搜索。

#20

#include<iostream>
using namespace std;
int BinarySearch(int *a,int key, int length)
{
    int l=0,r=length-1,res=-1;
    while(l<=r)
    {
        int mid = (l+r)/2;
        if(a[mid] == key) {res = mid; break;}
                //Check the part of the array that maintains sort sequence and update index                   
                // accordingly.
        if((a[mid] < a[r] && ( key > a[mid] && key <=a[r]))
            || a[mid] > a[r] && !( key>=a[l] && key <a[mid]))
        {
                     l = mid+1;
        }
        else r = mid-1;
    }
    return res;
}
void main()
{
    int arr[10] = {6,7,8,9,10,13,15,18,2,3};
    int key = 8;
    cout<<"Binary Search Output: "<<BinarySearch(arr,key,10);
}

#21

Find element index in rotated sorted array

查找旋转有序数组中的元素索引。

Example : [6,7,8,1,2,3,5]

int findElementIndex(int []a, int element, int start, int end)
{
    int mid = (start + end)>>1;

    if(start>end)
        return -1;

    if(a[mid] == element)
    return mid;

    if(a[mid] < a[start])
    {
       if(element <= a[end] && element > a[mid])
        {
       return findElementIndex(a,element,mid+1,end);
        }
        else{
       return findElementIndex(a,element,start,mid-1);
        }
     }
    else  if(a[mid] > a[start]){
        if(element >= a[start] && element < a[mid])
             return findElementIndex(a,element,start,mid-1);
        else
            return findElementIndex(a,element,mid+1,end);
    }
    else if (a[mid] == a[start]){
        if(a[mid] != a[end]) // repeated elements
          return findElementIndex(a,element,mid+1,end);
        else
            int left = findElementIndex(a,element,start,mid-1);
            int right = findElementIndex(a,element,mid+1,end);

            return (left != -1) ? left : right;

    }

}