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

이진 탐색은 정렬된 배열에서만 사용할 수 있으며 검색 간격을 반복적으로 반으로 나누어 가면서 탐색하는 탐색 알고리즘 중 하나입니다.

 

동작방식

1. 배열의 중간 인덱스인 mid, 탐색할 배열의 맨 왼쪽 인덱스인 left, 맨 오른쪽인 right를 계산해야합니다.

2. 중간 인덱스는 (left + right) / 2 로 계산합니다, 이 때 정수가 돼야함으로 소수점은 버립니다.

3. 배열의 mid번째 요소와 탐색 할 숫자를 비교합니다.

4. 탐색할 숫자가 더 크면, left를 mid + 1 번째 인덱스로 바꿔줍니다.

5. 탐색할 숫자가 더 작으면, right를 mid - 1 번째 인덱스로 바꿔줍니다.

6. 탐색 범위를 초과하기 전까지 반복합니다.

7. left가 right보다 크면 탐색할 범위를 초과한 것이므로 종료합니다.

 

복잡도

시간 복잡도: O(log N). 

 

코드

def binary_search(target_number):
    sorted_array = [1,2,3,4,5,6]

    left = 0
    right = len(sorted_array) - 1
    while(right >= left):
        mid = (left + right) // 2
        if(target_number == sorted_array[mid]):
            return target_number
        elif(target_number < sorted_array[mid]):
            right = mid - 1
        else:
            left = mid + 1
    return -1

print(binary_search(2))
print(binary_search(7))