시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 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
정렬 된 회전 배열에서 검색을위한 알고리즘
- 먼저 pivot 요소를 찾습니다. pivot 요소는 정렬 된 회전 된 배열의 배열 요소로, 두 인접 요소 (배열)가 그보다 작습니다. 기본적으로 피벗은 배열에서 가장 큰 요소입니다. pivotSearch ()는 피벗 인덱스를 반환합니다.
- 피벗이 발견되면 검색 할 요소의 값에 따라 이진 검색 범위 [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
복잡성 분석
- 시간 복잡도 T (n) = O (logn)
- 공간 복잡성 A (n) = O (1)
추가 정보 :
- 위의 알고리즘은 정렬 된 회전 배열에 중복 요소가 포함 된 경우 적용되지 않습니다.
