在圆形排序的数组Seaching一个元素

本文介绍了在圆形排序的数组Seaching一个元素的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我们要搜索​​一个给定的元素以圆形有序阵列中的复杂性并不比 O（log n）的更大。 示例：搜索 13 在 {5,9,13,1,3} 。

We want to search for a given element in a circular sorted array in complexity not greater than O(log n). Example: Search for 13 in {5,9,13,1,3}.

我的想法是圆形数组转换成常规排序的数组然后做所产生的阵列上的二进制搜索，但我的问题是算法，我想出了是愚蠢的，它需要 O（N） 在最坏的情况：

My idea was to convert the circular array into a regular sorted array then do a binary search on the resulting array, but my problem was the algorithm I came up was stupid that it takes O(n) in the worst case:

for(i = 1; i < a.length; i++){ if (a[i] < a[i-1]){ minIndex = i; break; } }

然后第i个元素的相应索引将从以下关系来确定：

then the corresponding index of ith element will be determined from the following relation:

(i + minInex - 1) % a.length

很显然，我的转换（从圆形到正规）算法可能需要为O（n），所以我们需要一个更好的。

it is clear that my conversion (from circular to regular) algorithm may take O(n), so we need a better one.

据ire_and_curses的想法，这里是Java的解决方案：

According to ire_and_curses idea, here is the solution in Java:

public int circularArraySearch(int[] a, int low, int high, int x){ //instead of using the division op. (which surprisingly fails on big numbers) //we will use the unsigned right shift to get the average int mid = (low + high) >>> 1; if(a[mid] == x){ return mid; } //a variable to indicate which half is sorted //1 for left, 2 for right int sortedHalf = 0; if(a[low] <= a[mid]){ //the left half is sorted sortedHalf = 1; if(x <= a[mid] && x >= a[low]){ //the element is in this half return binarySearch(a, low, mid, x); } } if(a[mid] <= a[high]){ //the right half is sorted sortedHalf = 2; if(x >= a[mid] && x<= a[high] ){ return binarySearch(a, mid, high, x); } } // repeat the process on the unsorted half if(sortedHalf == 1){ //left is sorted, repeat the process on the right one return circularArraySearch(a, mid, high, x); }else{ //right is sorted, repeat the process on the left return circularArraySearch(a, low, mid, x); } }

希望这会工作。

Hopefully this will work.

推荐答案

您可以通过利用一个事实，即数组排序，除了支点价值的特殊情况和它的邻国之一的优势做到这一点。

You can do this by taking advantage of the fact that the array is sorted, except for the special case of the pivot value and one of its neighbours.

• 找到的阵列。
的中间值
• 如果 A [0] LT;一个[MID] ，那么所有的值 第一阵列的一半是 排序。
• 如果 A [MID]＆LT;一个[最后] ，那么所有的 在对下半年的值 数组进行排序。
• 就拿排序 一半，并检查是否你的价值 就在于在它（比作 在半最大IDX）。
• 如果是这样，只是二进制 搜索一半。
• 如果不是这样，它 必须在未排序的一半。采取 一半并重复这一过程， 确定哪些一半一半 排序等。

• Find the middle value of the array a.
• If a[0] < a[mid], then all values in the first half of the array are sorted.
• If a[mid] < a[last], then all values in the second half of the array are sorted.
• Take the sorted half, and check whether your value lies within it (compare to the maximum idx in that half).
• If so, just binary search that half.
• If it doesn't, it must be in the unsorted half. Take that half and repeat this process, determining which half of that half is sorted, etc.