향상된 바이너리 검색

Question

인터뷰 준비 질문을하고 있는데이 문제를 보았습니다 : 정렬되고 회전 된 배열로 요소를 검색하십시오.는

나에게 가장 확실한 해결책은 분할 지점으로 알고있는 번호가 다음 번호)보다 큰 피벗 점을 (찾아 1)에, 그리고 2) 사용의 절반이 이진 검색을 실행하기 위해 회전 및 정렬 된 배열.

나는 "더 나은"(또는 괴짜를 괴롭히는 사람들이 주장하는) 해결책을 발견했습니다. 코드로 당신을 지루하게하지 않으려 고 여기에 높은 수준의 아이디어가 있습니다. 내 질문은 : 중간 지점을 찾는 것이 우리가 단 하나의 패스로 검색하는 방법을 이해하지 못합니다. 솔직히 내가 생각해 낸 초기 솔루션보다 더 나은 점이 있습니까?

높은 수준 "개선/더"접근 방식 :

이

1) Find middle point mid = (l + h)/2 
2) If key is present at middle point, return mid. 
3) Else If arr[l..mid] is sorted 
    a) If key to be searched lies in range from arr[l] 
     to arr[mid], recur for arr[l..mid]. 
    b) Else recur for arr[mid+1..r] 
4) Else (arr[mid+1..r] must be sorted) 
    a) If key to be searched lies in range from arr[mid+1] 
     to arr[r], recur for arr[mid+1..r]. 
    b) Else recur for arr[l..mid] 

Answer 1

귀하의 1 단계는 피벗 점을 찾을 수 있도록해야합니다. 그렇게하려면 검색이 필요합니다. 이 솔루션은 피벗 포인트에 대한 이진 검색과 대상에 대한 이진 검색을 결합합니다. 당신의 해결책은 그렇지 않습니다.