在排序的旋轉數組中搜索


難度級別
經常問 土磚 亞馬遜 蘋果 彭博社 ByteDance 易趣 Expedia的 Facebook 高盛 谷歌 Microsoft微軟 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)

補充資料:

  • 當排序的旋轉數組包含重複元素時,以上算法不適用。

參考