[알고리즘] 이분탐색(Binary Search)(이진탐색)

[이분탐색(이진탐색)의 정의]

: 오름차순으로 정렬된 리스트에서 찾고자 하는 값의 위치를 찾는 알고리즘

---

[이분탐색의 특징]

: 모든 값을 순회하는 일반탐색 보다 빠른 속도.

시간복잡도: O(logN)

---

[이분 탐색 진행 과정]

 

오름차순으로 정렬된 배열에서 특정 데이터를 탐색하는 상황

 

1. 오름차순으로 정렬된 배열에서 맨처음 값의 인덱스를 low라고 하고, 맨 뒤의 인덱스의 값을 high의 변수에 저장함. 

 

2.  배열의 중앙값을 선택: 중앙값은 mid가 된다. 

 

3. 중앙값과 특정 데이터의 값을 비교한다. 

만약, 중앙값보다 특정 데이터가 클 경우, 중앙값 오른쪽의 요소들을 선택하여 탐색한다. = 탐색을 대상 배열의 맨 처음 인덱스의 값(low)가 중앙값+1의 값을 가진다. 

 

(반대의 경우는 high가 중앙값-1의 값을 가짐)

 

4. 선택된 우측 요소의 중앙값을 선택한다. (mid갱신)

 

5. 중앙값과 특정 데이터를 비교한다.

만약, 특정 데이터가 중앙값 보다 클 경우,중앙값 오른쪽의 요소들을 선택하여 탐색한다. = 탐색을 대상 배열의 맨 처음 인덱스의 값(low)가 중앙값+1의 값을 가진다.

 

(반대의 경우는 high가 중앙값-1의 값을 가짐)

 

6. 남은 배열(2개)중에 좌측 요소를 선택하여 특정 데이터를 비교한다. 

만약 두 값이 같으면 탐색 종료 

 

---

[구현]

 

• 반복문
• 재귀

1. 탐색 대상값이 속한 자료를 오름차순으로 정렬한다. 

2. 자료의 중간값(mid)이 찾고자 하는 값(target)인지 비교한다. 

3. 중간값(mid)이 찾고자 하는 값(target)과 다르다면 대소관계를 비교하여 탐색 범위를 좁히고, target과 mid값이 같을 때까지 아래 조건에 따라 2번 3번을 반복한다. 

1. 찾고자 하는 값(target)이 중간값(mid)보다 작으면 end값을 mid-1의 값으로 바꾼다. 
2. 찾고자 하는 값(target)이 중간값(mid)보다 크면 high값을 mid+1의 값으로 바꾼다.