algorithm | array - binary search

> 동작원리

배열이 정렬되어 있을 때 특정 element를 찾아달라는 문제입니다.

O(logn)의 time complexity를 가집니다.

위와 같은 배열이 있는 경우 Left는 첫 인덱스를, Right는 끝 인덱스를 가리키며 Pivot은 Left+Right/2의 인덱스에 위치합니다.

이 때 22라는 숫자를 찾을 경우 Pivot을 기준으로 오른쪽에 위치한다는 것을 확인하게 됩니다.

이후 left는 기존 pivot의 인덱스보다 +1 된 곳으로 이동되며 pivot은 다시 left와 right의 중간으로 이동하게 됩니다.

그러면 우리가 찾고자 했던 22에 pivot이 위치하게 되었으므로 pivot을 리턴해 주게 됩니다.

grande말입니다.

만약 우리가 찾으려던 숫자가 위 배열에는 없는 23일 경우라면 어떻게 될까요?

23은 22보다 크기 때문에 left의 인덱스는 22에 있는 pivot보다 앞에 있는 30으로 이동합니다.

그리고 pivot 또한 30으로 이동합니다.

하지만 30은 우리가 찾는 23보다 크기 때문에 이번에는 right가 pivot보다 1 작은 인덱스로 이동합니다.

그리고 left와 right의 위치가 바뀌면서 우리가 찾는 23이 없다는 정보(-1)를 리턴하면서 알고리즘을 종료합니다.

---

> example code

array = [1, 2, 5, 9, 15, 22, 30]

my_number = int(input('찾으려는 숫자를 입력하세요.: '))

def binary_search(arr, target):
    left = 0
    right = len(arr) -1

    while left <= right:
        pivot = (left+right) // 2

        if arr[pivot] == target:
            return pivot
        elif arr[pivot] < target:
            left = pivot + 1
        else: # arr[pivot] > target
            right = pivot - 1
    
    return -1

print(f'입력한 숫자의 index는 {binary_search(array, my_number)}입니다.')

---

출처: 코드없는 프로그래밍