이진 탐색 ( Binary Search )

이진 탐색 ( Binary Search )

• 순차 탐색은 배열의 길이가 n이라면, 최악의 경우 $O(N)$ 의 시간이 걸림
• 이진 탐색은 탐색을 할 때, 탐색 범위를 1/2 씩 줄여나가며 탐색하는 방법
• 데이터가 정렬 되어 있을 때만 사용가능

동작 과정

• 데이터의 중앙값 선택
• 선택한 값과 찾고자 하는 값을 비교
• 비교결과를 통해 탐색범위 변경
  • 선택한 값이 더 작다면, 탐색 범위의 끝을 중앙-1로 변경하여 탐색범위를 왼쪽 반으로 줄임
  • 선택한 값이 더 크다면, 탐색 범위의 시작을 중앙+1로 변경하여 탐색범위를 오른쪽 반으로 줄임
  • 같다면, 종료
• 찾을 때까지 위 과정을 반복

시간복잡도 : $O(log_2N)$

구현

def binary_search(arr,start,end,find):
    if start > end:
        print("Not exist")
        return -1
	mid = (start+end)//2
    if arr[mid] == find:
        print("arr[%d]"%(mid))
        return
    if arr[mid] < find:
        return binary_search(arr,mid+1,end,find)
    if arr[mid] > find:
        return binary_search(arr,start,mid-1,find)

arr = [2, 4, 6, 8, 10, 12, 14, 16, 18, 20]
x = 6
binary_search(arr,0,len(arr),x)

Reference

• https://justicehui.github.io/easy-algorithm/2018/03/18/BinarySearch/