인터뷰를 준비하는 동안 다음과 같은 흥미로운 질문을 발견했습니다.
정렬 된 다음 회전 된 배열이 주어졌습니다.
예를 들면 :
arr = [1,2,3,4,5]정렬 된 Let ,- 제공하려면 오른쪽으로 두 번 회전하십시오
[4,5,1,2,3].이제이 정렬 된 + 회전 된 배열에서 하나의 검색이 얼마나 최선일까요?
배열을 회전 해제 한 다음 이진 검색을 수행 할 수 있습니다. 그러나 둘 다 최악의 경우 O (N)이기 때문에 입력 배열에서 선형 검색을 수행하는 것보다 낫지 않습니다.
몇 가지 지침을 제공하십시오. 나는 이것에 대한 특별한 알고리즘을 많이 봤지만 아무것도 찾을 수 없었다.
C와 C ++를 이해합니다.
답변
이것은 O(logN)약간 수정 된 이진 검색 을 사용하여 수행 할 수 있습니다 .
정렬 된 + 회전 된 배열의 흥미로운 속성은 두 개의 절반으로 나눌 때 두 절반 중 적어도 하나가 항상 정렬된다는 것입니다.
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
오른쪽 하위 배열은 정렬되지 않고 왼쪽 하위 배열은 정렬됩니다.
중간이 회전 지점 인 경우 왼쪽 및 오른쪽 하위 배열이 모두 정렬됩니다.
[6,7,8,9,1,2,3,4,5]
^
그러나 어쨌든 반 (하위 배열)은 정렬되어야합니다 .
각 절반의 시작 요소와 끝 요소를 비교하여 어느 절반이 정렬되었는지 쉽게 알 수 있습니다.
정렬 된 절반을 찾으면 그 절반에 키가 있는지 확인할 수 있습니다. 극단과의 간단한 비교입니다.
그 절반에 키가 있으면 우리는 그 절반에 대한 함수를
재귀 적으로 호출하고 나머지 절반에 대한 검색을 재귀 적으로 호출합니다.
우리는이 알고리즘을 만드는 각 호출에서 배열의 절반을 버립니다 O(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 half..search right half.
else
return search(arr,key,mid+1,high)
end-if
// if right 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
여기서 핵심은 하나의 하위 배열이 항상 정렬되어 배열의 절반을 버릴 수 있다는 것입니다.
답변
허용되는 답변에는 배열에 중복 요소가있을 때 버그가 있습니다. 예를 들어, arr = {2,3,2,2,2}3은 우리가 찾고있는 것입니다. 그런 다음 수락 된 답변의 프로그램은 1 대신 -1을 반환합니다.
이 인터뷰 질문은 ‘Cracking the Coding Interview’책에 자세히 설명되어 있습니다. 중복 요소의 조건은 그 책에서 특별히 논의됩니다. op가 주석에서 배열 요소가 무엇이든 될 수 있다고 말 했으므로 아래의 의사 코드로 솔루션을 제공하고 있습니다.
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
답변
인덱스를 찾을 수 첫째 : 당신은 2 개 진 검색 할 수있는 i그러한를 arr[i] > arr[i+1].
분명히, (arr\[1], arr[2], ..., arr[i])그리고 (arr[i+1], arr[i+2], ..., arr[n])둘 다 정렬 된 배열입니다.
그런 다음 arr[1] <= x <= arr[i]첫 번째 배열에서 이진 검색을 수행하고 그렇지 않으면 두 번째 배열에서 이진 검색을 수행합니다.
복잡성 O(logN)
편집 :
코드 .
답변
내 첫 번째 시도는 이진 검색을 사용하여 적용된 회전 수를 찾는 것입니다. 이것은 일반적인 이진 검색 메커니즘을 사용하여 a [n]> a [n + 1] 인 인덱스 n을 찾아서 수행 할 수 있습니다. 그런 다음 찾은 시프트 당 모든 인덱스를 회전하면서 일반 이진 검색을 수행합니다.
답변
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;
}
답변
배열이 s 오른쪽으로 회전 된 것을 알고 있다면 s를 오른쪽으로 이동시킨 이진 검색을 수행 할 수 있습니다. 이것은 O (lg N)
즉, 왼쪽 제한을 s로, 오른쪽을 (s-1) mod N으로 초기화하고 이진 검색을 수행하여 올바른 영역에서 작업하기 위해 약간의주의를 기울입니다.
배열이 얼마나 회전했는지 모르는 경우 이진 검색 (O (lg N))을 사용하여 회전의 크기를 확인한 다음 이동 이진 검색, O (lg N), a 여전히 O (lg N)의 총합.
답변
얼마나 (멀리) 회전했는지 안다면 이진 검색을 할 수 있습니다.
비결은 두 가지 수준의 인덱스를 얻는 것입니다. 가상 0..n-1 범위에서 bs를 수행 한 다음 실제로 값을 찾을 때 회전을 해제합니다.