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

💡이분 탐색 알고리즘이란

• 이분 탐색 알고리즘은 정렬된 리스트에서 검색 범위를 반으로 줄여 나가면서 검색 값을 찾는 알고리즘입니다.
• 이분 탐색은 배열 내부의 데이터가 정렬(오름차순)되어 있어야만 사용할 수 있는 알고리즘이다.
• BigO : O(log N)
• 반드시 정렬된 상태에서 시작해야하므로 로그실행시간을 보장합니다.

 

구현에 필요한 데이터

• Start : data의 처음 값 인덱스
• Mid : Start, End 합의 중간 인덱스
• End : data의 마지막 값 인덱스
• Target : 찾고자 하는 값
• data : 오름차순으로 정렬된 리스트

 

구현 방법

1. 리스트가 정렬된 상태인지 확인합니다.

2. start, end, mid, target 을 확입합니다.

3. 찾고자하는 target이 mid값보다 크면 오른쪽 범위에서 다시 찾고 작으면 왼쪽 범위에서 찾습니다, 만약 target과 mid가 같아지면 값을 출력합니다.

4. 반복문과 재귀로도 구현 가능합니다.

 

 

예제 코드(반복문)

 

 

예제 코드(재귀함수)

 

위의 코드는 재귀함수로 이분 탐색코드를 구현한 방법입니다.

 

1. low가 high보다 크면, 배열에서 대상 값을 찾을 수 없기 때문에 -1을 반환합니다.

2. mid 인덱스를 계산합니다. ( mid = (low + high) // 2)

3. arr[mid]가 대상 값과 같으면 mid를 반환합니다.

4. arr[mid]가 대상 값보다 작으면, 함수를 재귀적으로 arr[mid+1:high] 범위에서 호출합니다.

5. arr[mid]가 대상 값보다 크면, 함수를 재귀적으로 arr[low:mid-1] 범위에서 호출합니다.

 

 

 

 

Reference

- 이진 탐색 : https://wayhome25.github.io/cs/2017/04/15/cs-16/

강의노트 15-2. [탐색] 이진탐색(Binary Search) 알고리즘 · 초보몽키의 개발공부로그