[알고리즘] 6. 이진탐색

• 이진탐색: 탐색 범위를 1/2씩 줄여나가는 알고리즘

 

• 과정

1. 데이터 집합의 중앙에 있는 요소를 고른다.

2. 중앙 요소의 값과 찾고자 하는 목표 값을 비교.

3. 목표값 < 중앙값 이면 중앙값 왼편 탐색/ 목표값 > 중앙값이면 중앙값 오른편 탐색

4.  목표값이 나올때까지 1~3과정 반복 

 

• 이진 탐색의 반복 횟수(데이터 개수 n개일 때) : log2n

-> 데이터 집합의 크기가 아무리 커져도 탐색 소요 시간은 아주 미미하게 증가한다는 것을 의미

 

**이진탐색 그냥 구현한 것도 작성해서 올리기**

 

 

• bsearch()함수로 이진탐색 구현