在sorting和旋转数组中search
在准备面试科技时，我偶然发现了一个有趣的问题：
你已经得到了一个sorting，然后旋转的数组。
例
让arr = [1,2,3,4,5]这是sorting，然后旋转说两次向右给
[4,5,1,2,3]
现在，如何在这个有序的+旋转的数组中search最好？
可以不旋转数组，然后执行二进制search。 但是，在input数组中进行线性search并不比在最坏情况下O（N）好。
请提供一些指示。 我已经search了很多特殊的algorithm，但找不到任何。
我理解c和c ++
这可以使用稍微修改的二进制search在O(logN)完成。
有序的+旋转数组的有趣属性是，当你把它分成两半时，至less有一半将总是被sorting。
Let input array arr = [4,5,6,7,8,9,1,2,3] number of elements = 9 mid index = (0+8)/2 = 4 [4,5,6,7,8,9,1,2,3] ^ left mid right
因为看起来正确的子数组没有sorting，而左子数组sorting。
如果mid恰好是旋转点，那么左边和右边的子数组将被sorting。
[6,7,8,9,1,2,3,4,5] ^
但在任何情况下，一半（子arrays）必须sorting 。
通过比较每一半的开始和结束元素，我们可以很容易地知道哪一半是sorting的。
一旦我们发现哪一半被分类，我们就可以看出这个关键是否存在于这个半个简单的比较中。
如果钥匙出现在那一半，我们recursion地调用那一半的function
否则我们recursion地调用另一半的search。
我们丢弃每个调用中的数组的一半，使得这个algorithmO(logN) 。
伪代码：
function search( arr[], key, low, high) mid = (low + high) / 2 // key not present if(low > high) return -1 // key found if(arr[mid] == key) return mid // if left half is sorted. if(arr[low] <= arr[mid]) { // if key is present in left half. if (arr[low] <= key && arr[mid] >= key) return search(arr,key,low,mid-1) // if key is not present in left hald..search right half. else return search(arr,key,mid+1,high) end-if // if righ half is sorted. else // if key is present in right half. if(arr[mid] <= key && arr[high] >= key) return search(arr,key,mid+1,high) // if key is not present in right half..search in left half. else return search(arr,key,low,mid-1) end-if end-if end-function
这里的关键是一个子数组将总是被sorting，使用它我们可以丢弃数组的一半。
你可以做2个二进制search：首先find索引i ，使得arr[i] > arr[i+1] 。
显然， (arr\[1], arr[2], ..., arr[i])和(arr[i+1], arr[i+2], ..., arr[n])都是sorting的数组。
那么如果arr[1] <= x <= arr[i] ，则在第一个数组处进行二分search，否则在第二个数组处search。
复杂度O(logN)
编辑： 代码 。
当数组中有重复的元素时，所选的答案有一个错误。 例如， arr = {2,3,2,2,2}和3是我们正在寻找的。 然后程序在选定的答案将返回-1而不是1。
这个面试问题在“破解编码面试”一书中有详细的讨论。 该书重点讨论了重复元素的条件。 由于op在评论中说数组元素可以是任何东西，我在下面给我的解决scheme作为伪代码：
function search( arr[], key, low, high) if(low > high) return -1 mid = (low + high) / 2 if(arr[mid] == key) return mid // if the left half is sorted. if(arr[low] < arr[mid]) { // if key is in the left half if (arr[low] <= key && key <= arr[mid]) // search the left half return search(arr,key,low,mid-1) else // search the right half return search(arr,key,mid+1,high) end-if // if the right half is sorted. else if(arr[mid] < arr[low]) // if the key is in the right half. if(arr[mid] <= key && arr[high] >= key) return search(arr,key,mid+1,high) else return search(arr,key,low,mid-1) end-if else if(arr[mid] == arr[low]) if(arr[mid] != arr[high]) // Then elements in left half must be identical. // Because if not, then it's impossible to have either arr[mid] < arr[high] or arr[mid] > arr[high] // Then we only need to search the right half. return search(arr, mid+1, high, key) else // arr[low] = arr[mid] = arr[high], we have to search both halves. result = search(arr, low, mid-1, key) if(result == -1) return search(arr, mid+1, high, key) else return result end-if end-function
我的第一个尝试是find使用二进制search应用的旋转次数 – 这可以通过使用通常的二进制search机制find索引n，其中a [n]> a [n + 1]来完成。 然后在find每个class次的所有索引的同时进行常规二分search。
如果你知道数组已经被向右旋转了，你可以简单地做一个二进制search向右移动。 这是O（lg N）
我的意思是，把左边限制初始化为（s-1）mod N的左边界，然后在这两个边界之间进行二分search，花点时间在正确的区域工作。
如果你不知道数组被旋转了多less，你可以使用二进制search来确定旋转有多大，即O（lg N），然后进行移位二进制search，O（lg N），a总共O（lg N）还是。
如果你知道（远）旋转，你仍然可以做一个二进制search。
诀窍是你得到两个级别的索引：你在虚拟的0..n-1范围内执行bs，然后在实际查找值时取消旋转它们。
你不需要先旋转数组，你可以在旋转的数组上使用二进制search（有一些修改）
假设N是您search的数字：
读取第一个数字（arr [start]）和数组中间的数字（arr [end]）：
-
如果arr [开始]> arr [end] – >前半部分没有sorting，但后半部分sorting：
-
如果arr [end]> N – >数字在index：（middle + N – arr [end]）
-
如果N重复search数组的第一部分（请参阅结尾是数组的前半部分的中间等）
-
（如果第一部分是sorting的，但第二部分不是）
int rotated_binary_search(int A[], int N, int key) { int L = 0; int R = N - 1; while (L <= R) { // Avoid overflow, same as M=(L+R)/2 int M = L + ((R - L) / 2); if (A[M] == key) return M; // the bottom half is sorted if (A[L] <= A[M]) { if (A[L] <= key && key < A[M]) R = M - 1; else L = M + 1; } // the upper half is sorted else { if (A[M] < key && key <= A[R]) L = M + 1; else R = M - 1; } } return -1; }
回复上面提到的post“这个采访问题在”编码采访的破解“一书中有详细的讨论，重复元素的条件在这本书中有特别的讨论，因为op在评论中说数组元素可以是任何东西，在下面给我的解决scheme作为伪代码：“
你的解决scheme是O（N）！ （最后一个条件，如果你检查一个单一的条件数组的两半，使其成为线性时间复杂度的一个解决scheme）
我在线性search上比在编码轮回中陷入错误和分段错误的迷宫更好。
我不认为有一个比O（n）更好的解决scheme在旋转的sorting数组中search（重复）
public class PivotedArray { //56784321 first increasing than decreasing public static void main(String[] args) { // TODO Auto-generated method stub int [] data ={5,6,7,8,4,3,2,1,0,-1,-2}; System.out.println(findNumber(data, 0, data.length-1,-2)); } static int findNumber(int data[], int start, int end,int numberToFind){ if(data[start] == numberToFind){ return start; } if(data[end] == numberToFind){ return end; } int mid = (start+end)/2; if(data[mid] == numberToFind){ return mid; } int idx = -1; int midData = data[mid]; if(numberToFind < midData){ if(midData > data[mid+1]){ idx=findNumber(data, mid+1, end, numberToFind); }else{ idx = findNumber(data, start, mid-1, numberToFind); } } if(numberToFind > midData){ if(midData > data[mid+1]){ idx = findNumber(data, start, mid-1, numberToFind); }else{ idx=findNumber(data, mid+1, end, numberToFind); } } return idx; } }
short mod_binary_search( int m, int *arr, short start, short end) { if(start <= end) { short mid = (start+end)/2; if( m == arr[mid]) return mid; else { //First half is sorted if(arr[start] <= arr[mid]) { if(m < arr[mid] && m >= arr[start]) return mod_binary_search( m, arr, start, mid-1); return mod_binary_search( m, arr, mid+1, end); } //Second half is sorted else { if(m > arr[mid] && m < arr[start]) return mod_binary_search( m, arr, mid+1, end); return mod_binary_search( m, arr, start, mid-1); } } } return -1; }
首先，你需要find移位常数k。 这可以在O（lgN）时间完成。 从常数k，你可以很容易地find你正在寻找的元素使用二进制search常数k。 增加的二进制search也需要O（lgN）时间总运行时间为O（lgN + lgN）= O（lgN）
为了find恒定的转移，k。 你只需要在数组中寻找最小值。 数组最小值的索引告诉你不断的移位。 考虑sorting的数组[1,2,3,4,5]。
可能的变化是：
[1,2,3,4,5] // k = 0
[5,1,2,3,4] // k = 1
[4,5,1,2,3] // k = 2
[3,4,5,1,2] // k = 3
[2,3,4,5,1] // k = 4
[1,2,3,4,5] // k = 5％5 = 0
要在O（lgN）时间内完成任何algorithm，关键是总能find将问题分成一半的方法。 一旦这样做，其余的实现细节很容易
下面是该algorithm的C ++代码
// This implementation takes O(logN) time // This function returns the amount of shift of the sorted array, which is // equivalent to the index of the minimum element of the shifted sorted array. #include <vector> #include <iostream> using namespace std; int binarySearchFindK(vector<int>& nums, int begin, int end) { int mid = ((end + begin)/2); // Base cases if((mid > begin && nums[mid] < nums[mid-1]) || (mid == begin && nums[mid] <= nums[end])) return mid; // General case if (nums[mid] > nums[end]) { begin = mid+1; return binarySearchFindK(nums, begin, end); } else { end = mid -1; return binarySearchFindK(nums, begin, end); } } int getPivot(vector<int>& nums) { if( nums.size() == 0) return -1; int result = binarySearchFindK(nums, 0, nums.size()-1); return result; } // Once you execute the above, you will know the shift k, // you can easily search for the element you need implementing the bottom int binarySearchSearch(vector<int>& nums, int begin, int end, int target, int pivot) { if (begin > end) return -1; int mid = (begin+end)/2; int n = nums.size(); if (n <= 0) return -1; while(begin <= end) { mid = (begin+end)/2; int midFix = (mid+pivot) % n; if(nums[midFix] == target) { return midFix; } else if (nums[midFix] < target) { begin = mid+1; } else { end = mid - 1; } } return -1; } int search(vector<int>& nums, int target) { int pivot = getPivot(nums); int begin = 0; int end = nums.size() - 1; int result = binarySearchSearch(nums, begin, end, target, pivot); return result; }
希望这有助于！=） 不久Chee Loong， 多伦多大学
这是一个简单的（时间，空间）高效的非recursionO（log n）python解决scheme，它不修改原始数组。 将旋转的数组切成两半，直到我只有两个索引来检查并返回一个索引匹配的正确答案。
def findInRotatedArray(array, num): lo,hi = 0, len(array)-1 ix = None while True: if hi - lo <= 1:#Im down to two indices to check by now if (array[hi] == num): ix = hi elif (array[lo] == num): ix = lo else: ix = None break mid = lo + (hi - lo)/2 print lo, mid, hi #If top half is sorted and number is in between if array[hi] >= array[mid] and num >= array[mid] and num <= array[hi]: lo = mid #If bottom half is sorted and number is in between elif array[mid] >= array[lo] and num >= array[lo] and num <= array[mid]: hi = mid #If top half is rotated I know I need to keep cutting the array down elif array[hi] <= array[mid]: lo = mid #If bottom half is rotated I know I need to keep cutting down elif array[mid] <= array[lo]: hi = mid print "Index", ix
另一种可以处理重复值的方法是find旋转，然后每当我们访问数组时进行常规二进制search。
test = [3, 4, 5, 1, 2] test1 = [2, 3, 2, 2, 2] def find_rotated(col, num): pivot = find_pivot(col) return bin_search(col, 0, len(col), pivot, num) def find_pivot(col): prev = col[-1] for n, curr in enumerate(col): if prev > curr: return n prev = curr raise Exception("Col does not seem like rotated array") def rotate_index(col, pivot, position): return (pivot + position) % len(col) def bin_search(col, low, high, pivot, num): if low > high: return None mid = (low + high) / 2 rotated_mid = rotate_index(col, pivot, mid) val = col[rotated_mid] if (val == num): return rotated_mid elif (num > val): return bin_search(col, mid + 1, high, pivot, num) else: return bin_search(col, low, mid - 1, pivot, num) print(find_rotated(test, 2)) print(find_rotated(test, 4)) print(find_rotated(test1, 3))
试试这个解决scheme
bool search(int *a, int length, int key) { int pivot( length / 2 ), lewy(0), prawy(length); if (key > a[length - 1] || key < a[0]) return false; while (lewy <= prawy){ if (key == a[pivot]) return true; if (key > a[pivot]){ lewy = pivot; pivot += (prawy - lewy) / 2 ? (prawy - lewy) / 2:1;} else{ prawy = pivot; pivot -= (prawy - lewy) / 2 ? (prawy - lewy) / 2:1;}} return false; }
对于带有重复项的旋转数组，如果需要查找元素的第一个匹配项，可以使用下面的过程（Java代码）：
public int mBinarySearch(int[] array, int low, int high, int key) { if (low > high) return -1; //key not present int mid = (low + high)/2; if (array[mid] == key) if (mid > 0 && array[mid-1] != key) return mid; if (array[low] <= array[mid]) //left half is sorted { if (array[low] <= key && array[mid] >= key) return mBinarySearch(array, low, mid-1, key); else //search right half return mBinarySearch(array, mid+1, high, key); } else //right half is sorted { if (array[mid] <= key && array[high] >= key) return mBinarySearch(array, mid+1, high, key); else return mBinarySearch(array, low, mid-1, key); } }
这是对上面codaddict程序的改进。 注意附加的条件如下：
if (mid > 0 && array[mid-1] != key)
