02. Binary Search (이진 탐색)

이진 탐색이란?

 - 시간복잡도 O(logN)를 지닌 탐색 방법이다.

 - 선형 탐색(순차 탐색)에 비해 빠른 검색을 할 수 있다.

 - 대상이 정렬된 상태여야 한다.

 

위의 그림을 예시로 이야기하면 다음 단계를 거친다.

1. left = 0 , right = 5 ====> pivot = 2  

 -> 그래서 array[2]의 value인 3과 target 9를 비교해서 target이 크므로 left를 3으로 변경한다.

2. left = 3 right = 5 =====> pivot = 4

 -> array[4]의 값이 target과 일치하므로 find를 하게 된다.

 

  만약 값을 찾지 못하는 상황은 left <= right이다. 이 경우에는 처리를 해주면 된다.

 

실제 예시

https://minteul.tistory.com/entry/01-LeetCode-704-Binary-Search

01. LeetCode 704 - Binary Search