Binary Search ( 이진탐색 )

오늘은 이진탐색 (이분탐색)에 대해 공부해보자

 

#1 개념

- 이진 탐색 알고리즘은 리스트 탐색 방법(선형탐색,이진탐색) 중 하나이며 이분탐색이라고도 한다.

 

- 이진탐색 알고리즘은 오름차순으로 정렬된 정수의 리스트를 중앙값(절반)으로 계속 나누어, 원하는 원소를 찾을 때 까지 탐색하는 방법이다.

 

- 절반을 나눌 때, 그 중앙값이 타겟원소와 일치한지, 큰지, 작은지 판별하여 일치하면 출력하고 아니면 계속 절반씩 나누며 반복한다.

 

#2 이진탐색 동작과정

1) 리스트를 먼저 오름차순한다.

2) 중앙값을 구하고 타겟 밸류와 비교하여,

 

 - Target < 중앙값 : 오른쪽 범위를 날린다.
 - Target > 중앙값 : 왼쪽 범위를 날린다.

 

3) 또 중앙값을 구하고 타겟밸류와 비교한다.

4) 그렇게 범위를 좁혀나가며 중앙값이 타겟밸류와 일치할때까지 탐색해나간다.

 

아래 사진을 참고하여 개념을 더욱 이해해보자.

그리고 본인이 실제로 익힌 실전코드도 참고해보면 도움이 될 것이다.

 

-> 이진탐색 실전 코딩링크 (깃허브)

 https://github.com/seokjunHwang/Algorithm_Training/tree/main/binary%20search

 

출처) https://namu.wiki/w/%EC%9D%B4%EC%A7%84%20%ED%83%90%EC%83%89