在排序的旋转数组中搜索


难度级别 中等
经常问 土砖 亚马逊 Apple 彭博 ByteDance 易趣 Expedia的 Facebook 高盛 谷歌 微软 Nvidia公司 神谕 贝宝 VMware的 沃尔玛实验室
排列 二进制搜索 排序

元素搜索按顺序旋转 排列 可以在O(logn)时间使用二进制搜索找到。 这篇文章的目的是要在O(logn)时间的旋转数组中找到给定的元素。 给出了旋转数组排序的一些示例。

使用案列

Input  : arr[] = {7,8,9,10,1,2,3,5,6};
         key = 2
Output : Found at index 5

Input  : arr[] = {7,8,9,10,1,2,3,5,6};
         key = 30
Output : Not found

Input : arr[] = {4,8,16,1,2}
        key = 2   
Output : Found at index 4

排序旋转数组中的搜索算法

  1. 我们首先找到数据透视元素,数据透视元素是排序后的旋转数组中的两个数组元素,其两个邻居(数组中)均小于它。 基本上,枢轴是数组中最大的元素。 ivotSearch()返回数据透视表的索引。
  2. 找到枢轴后,我们将根据要搜索的元素的值执行二进制搜索范围[0,p]或范围[p,n-1]。

这里,

p =枢轴索引

n =数组的大小

arr[] = {7,8,9,10,1,2,3,5,6}
Element to Search = 2
  1.find out pivot p and divide the array into two subarrays range[lo,p] and range[p,hi]
  2.perform binary search in one of the subarrays.
      a. if key >= arr[0], call binary search in range[lo,p].
      b. else call binary search in range[p,hi]
  3.if key is found in selected sub-array then return it's index 
       else return -1.

lo(index number of first array element) = 0
hi(index number of last array element) = n-1
p = index of pivot
n = size of the array

在排序的旋转数组中搜索

实施

C ++程序

#include <bits/stdc++.h> 
using namespace std; 

// Standard Binary Search function
int binarySearch(int arr[],int lo,int hi,int key) 
{ 
    if (lo <= hi)
    {
        int mid = (lo+hi)/2; /*low + (high - low)/2;*/
        
        if (key == arr[mid]) 
        	return mid; 
        	
        if (key > arr[mid]) 
        	return binarySearch(arr,mid+1,hi,key);
        	
        else
        	return binarySearch(arr,lo,mid-1,key); 
    }
    
    return -1;  // low > high
} 

/* Function to get pivot. For sorted rotated array 7,9,11,12,1,3 it returns 3 (index of 12) */
int pivotSearch(int arr[],int lo,int hi) 
{ 
    // base cases
    if (hi < lo) 
    return -1;      // if array is not rotated at all
    if (hi == lo) 
    return lo; 
    
    int mid = (lo+hi)/2; /*lo + (hi-lo)/2;*/
    
    // pivot is greater than array element to it's right
    if (mid < hi && arr[mid] > arr[mid+1]) 
    	return mid; 
    // pivot is greater than array element to it's left
    if (mid > lo && arr[mid] < arr[mid-1]) 
    	return (mid-1); 
    	
    
    if (arr[lo] >= arr[mid]) 
    	return pivotSearch(arr,lo,mid-1);   // pivot lies in left half 
    else
        return pivotSearch(arr,mid+1,hi);   // pivot lies in right half
    
} 

int pivotedBinarySearch(int arr[],int n,int key) 
{ 
    int pivot = pivotSearch(arr,0,n-1); // obtain the pivot index 
    
    // If no pivot is found,then array is not rotated at all 
    // in this case we perform a simple binary search as array is sorted (but not rotated)
    if (pivot == -1) 
    	return binarySearch(arr,0,n-1,key); 
    
    // If we found a pivot, then first compare with pivot value 
    if (arr[pivot] == key) 
    	return pivot; 
    
    // else perform binary search in two subarrays around pivot 
    
    // if element to be searched is greater than first (0-index) array element
    // then searched element lies between indices - 0 and pivot
    if (arr[0] <= key) 
    	return binarySearch(arr,0,pivot-1,key);
    // else it lies between indices - pivot and n-1
    else	
    	return binarySearch(arr,pivot+1,n-1,key);
} 

/* Main program to implement above functions */
int main() 
{ 
    // element to be searched = 3 
    int arr[] = {7,8,9,10,1,2,3,5,6}; 
    int n = sizeof(arr)/sizeof(arr[0]); 
    int search = 2; 
    	
    cout << "Index of "<<search<<" : "<<pivotedBinarySearch(arr,n,search); 
    			
    return 0; 
} 
Index of 2 : 5

Java程序

class sortedRotatedSearch 
{ 
    // Standard Binary Search function
    static int binarySearch(int arr[],int lo,int hi,int key) 
    { 
        if (lo <= hi)
        {
            int mid = (lo+hi)/2; /*low + (high - low)/2;*/
            
            if (key == arr[mid]) 
            	return mid; 
            	
            if (key > arr[mid]) 
            	return binarySearch(arr,mid+1,hi,key);
            	
            else
            	return binarySearch(arr,lo,mid-1,key); 
        }
        
        return -1;  // low > high
    } 
    
    /* Function to get pivot. For sorted rotated array 7,9,11,12,1,3 it returns 3 (index of 12) */
    static int pivotSearch(int arr[],int lo,int hi) 
    { 
        // base cases
        if (hi < lo) 
        return -1;      // if array is not rotated at all
        if (hi == lo) 
        return lo; 
        
        int mid = (lo+hi)/2; /*lo + (hi-lo)/2;*/
        
        // pivot is greater than array element to it's right
        if (mid < hi && arr[mid] > arr[mid+1]) 
        	return mid; 
        // pivot is greater than array element to it's left
        if (mid > lo && arr[mid] < arr[mid-1]) 
        	return (mid-1); 
        	
        
        if (arr[lo] >= arr[mid]) 
        	return pivotSearch(arr,lo,mid-1);   // pivot lies in left half 
        else
            return pivotSearch(arr,mid+1,hi);   // pivot lies in right half
        
    } 
    
    // function to search an element in sorted-rotated array
    static int pivotedBinarySearch(int arr[],int n,int key) 
    { 
        int pivot = pivotSearch(arr,0,n-1); // obtain the pivot index 
        
        // If no pivot is found,then array is not rotated at all 
        // in this case we perform a simple binary search as array is sorted (but not rotated)
        if (pivot == -1) 
        	return binarySearch(arr,0,n-1,key); 
        
        // If we found a pivot, then first compare with pivot value 
        if (arr[pivot] == key) 
        	return pivot; 
        
        // else perform binary search in two subarrays around pivot 
        
        // if element to be searched is greater than first (0-index) array element
        // then searched element lies between indices - 0 and pivot
        if (arr[0] <= key) 
        	return binarySearch(arr,0,pivot-1,key);
        // else it lies between indices - pivot and n-1
        else	
        	return binarySearch(arr,pivot+1,n-1,key);
    } 
    
    // main function to implement above function 
    public static void main(String args[]) 
    { 
       // Let us search 3 in below array 
       int arr[] = {7,8,9,10,1,2,3,5,6};
       int n = arr.length; 
       int key = 2; 
       System.out.println("Index of "+key+" is : "+ pivotedBinarySearch(arr,n,key)); 
    } 
}
Index of 2 is : 5

用于排序旋转阵列的改进的搜索解决方案/算法

我们可以通过一次遍历来搜索sorted-rotated数组中的元素 二进制搜索。 这个想法是寻找被搜索元素可以位于其中的特定范围的排序数组元素。 找到这样的范围后,我们将在该范围内执行二进制搜索以查找搜索到的元素。 下面是过程:

假设“键”是要搜索的元素。

1. find mid point of the range [lo,hi] as mid = (lo+hi)/2
2. if arr[mid] == key : return mid.
3. else if range [lo,mid-1] is sorted
    a. if arr[lo] <= key <= arr[mid],search for key in range[lo,mid].
    b. else recur for range [mid+1,hi].
4. else range[mid+1,hi] must be sorted
    a. if arr[mid+1] <= search <= arr[hi],search for key range[mid+1,hi].
    b. else recur for range [lo,mid].

以下是上述内容的C ++和Java实现 算法.

实施

C ++程序

#include <bits/stdc++.h> 
using namespace std; 

// Returns index of searched element 'key' in arr[lo,hi] if key is present 
// or else returns -1 
int find(int arr[],int lo,int hi,int key) 
{ 
  if (lo > hi) 
  return -1; 

  int mid = (lo+hi)/2; 
  
  if (arr[mid] == key) 
  return mid; 

  // if arr[lo,mid-1] is sorted
  if (arr[lo] <= arr[mid]) 
  {
    if (key >= arr[lo] && key <= arr[mid]) 
    return find(arr,lo,mid-1,key);      // check if key lies in range[lo,mid-1]
    
    else
    return find(arr,mid+1,hi,key);      // else recur for range[mid+1,hi]
  } 
    // else arr[mid+1,hi] must be sorted
    else
    {
    	if (key >= arr[mid] && key <= arr[hi]) 
    	return find(arr,mid+1,hi,key);         // check if key lies in range[mid+1,hi]
        
        else
    	return find(arr,lo,mid-1,key);         // else recur for range[lo,mid-1]
    }
} 

// Main Program to implement above functions
int main() 
{ 
  int arr[] = {7,8,9,10,1,2,3,5,6};
  int n = sizeof(arr)/sizeof(arr[0]); 
  int key = 2; 
  int i = find(arr, 0, n-1, key); 

  i != -1 ? cout<<"Index of "<<key<<" : "<<i<<endl : cout<<"Element Not found";
} 
Index of 2 : 5

Java程序

class sortedRotatedSearch 
{ 
    // Returns index of searched element 'key' in arr[lo,hi] if key is present 
    // or else returns -1 
    static int find(int arr[],int lo,int hi,int key) 
    { 
    	if (lo > hi) 
    	return -1; 
    
    	int mid = (lo+hi)/2; 
    	
    	if (arr[mid] == key) 
    	return mid; 
    
    	// if arr[lo,mid-1] is sorted
    	if (arr[lo] <= arr[mid]) 
    	{
    		if (key >= arr[lo] && key <= arr[mid]) 
    		return find(arr,lo,mid-1,key);      // check if key lies in range[lo,mid-1]
    		
    		else
    		return find(arr,mid+1,hi,key);      // else recur for range[mid+1,hi]
    	} 
        // else arr[mid+1,hi] must be sorted
        else
        {
        	if (key >= arr[mid] && key <= arr[hi]) 
        	return find(arr,mid+1,hi,key);         // check if key lies in range[mid+1,hi]
            
            else
        	return find(arr,lo,mid-1,key);         // else recur for range[lo,mid-1]
        }
    } 

    // Main Program to implement above functions
    public static void main(String args[]) 
    { 
    	int arr[] = {7,8,9,10,1,2,3,5,6};
    	int n = arr.length; 
    	int key = 2; 
    	int i = find(arr,0,n-1,key); 
    
    	if (i != -1)  
            System.out.println("Index of "+key+" : "+i); 
        else
            System.out.println("Key not found"); 
    } 
} 
Index of 2 : 5

复杂度分析

  1. 时间复杂度T(n)= O(logn)
  2. 空间复杂度A(n)= O(1)

补充资料:

  • 当排序后的旋转数组包含重复元素时,以上算法不适用。

參考資料