[알고리즘] Binary search: divide-and-conquer

(2021.10.10)

알고리즘 수업들으면서 정리하기 9탄

5주차 내용-3 마지막!!!

 

 

---

Binary search

주어진 배열에서 찾고자하는 값이 있는 인덱스를 찾는 problem 이다.

 

 

 

Divide-and-conquer approach

• Divide A[1..n] into two parts A[1..mid-1] and A[mid+1..n]
• Conquer: if A[mid]=x, return mid             if A[mid]<x, return A[mid+1..n] for next iteration             if A[mid]>x, return A[1..mid-1] for next iteration
• Combine: just return the result

(key: can reduce the array to it's half for the next iteration)

 

 

 

 

BINARY_SEARCH(A,low,high,key)
  n=(low+high)/2
  mid=A[n]
  
  if (key=A[n]) return n
  else if (key<A[n]) return BINARY_SEARCH(A,low,n-1,key)
  else return BINARY_SEARCH(A,n+1,high,key)

 

 

 

 

Divide-and-conquer 를 이용하여 binary search의 T(n) 계산

 

 

 

 

 

 

 

 

 

 

divide-and-conquer 의 최종 정리