1_6 자료구조와 알고리즘의 이해

1. 이진 탐색 알고리즘의 구현 1

- First와 Last가 만났다는 것은 탐색 대상이 하나 남았다는 것을 뜻함!

- 따라서 First와 Last가 역전될 때까지 탐색의 과정을 계속해서 진행한다.

 

 

※ 이진 탐색의 기본 골격

 

 

 

2. 이진 탐색 알고리즘의 구현 2

* last와 first에 왜 +1, -1을 해주는 것일까?

 => -1 혹은 +1을 추가하지 않으면 first <= mid <= last가 항상 성립이 되어, 탐색 대상이 존재하지 않는 경우 first와 last의 역전 현상이 발생하지 않는다. 즉, 항상 first <= mid <= last 가 항상 적용이 된다. 

 

연산 순서

1. (First + Last) / 2

2. 중간값보다 큰지 작은지 비교한다.

3. 왼쪽으로 갈지 오른쪽으로 갈지 결정한다.

4. 탐색 대상이 나올때까지 반복