정렬 된 회전 배열에서 검색

난이도 중급
자주 묻는 질문 어도비 벽돌 아마존 Apple 블룸버그 게시물에서 ByteDance 이베이 Expedia Facebook 골드만 삭스 구글 Microsoft 엔비디아 신탁 페이팔 VM웨어 월마트 연구소
배열 이진 검색 정렬조회수 71

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

회전 정렬 된 요소 검색 정렬 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. 먼저 pivot 요소를 찾습니다. pivot 요소는 정렬 된 회전 된 배열의 배열 요소로, 두 인접 요소 (배열)가 그보다 작습니다. 기본적으로 피벗은 배열에서 가장 큰 요소입니다. pivotSearch ()는 피벗 인덱스를 반환합니다.
  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

자바 프로그램

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

정렬 된 회전 배열에서 검색을위한 개선 된 솔루션 / 알고리즘

한 번의 패스로 정렬 된 회전 배열의 요소를 검색 할 수 있습니다. 이진 검색. 아이디어는 검색된 요소가 놓일 수있는 정렬 된 배열 요소의 특정 범위를 찾는 것입니다. 이러한 범위를 찾으면 해당 범위에서 이진 검색을 수행하여 검색된 요소를 찾습니다. 다음은 프로세스입니다.

'key'가 검색 할 요소라고 가정합니다.

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

자바 프로그램

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)

추가 정보 :

  • 위의 알고리즘은 정렬 된 회전 배열에 중복 요소가 포함 된 경우 적용되지 않습니다.

참조

균열 시스템 설계 인터뷰
Translate »