[swift & python] 이진탐색 Binary Search

개린이가 쓴 글이므로 오류가 있을 수 있음을 미리 알려드립니다 🐹 (꾸벅)

🐹 이진탐색?

오늘은 이진탐색에 대해 공부를 해보겠습니다.
일반적으로 자주 쓰이는 배열의 첫번째 숫자부터 하나하나 탐색하는 것을
선형탐색이라고 합니다.

선형탐색은 $O(N)$ 의 시간복잡도를 가지고 있습니다.

오늘 알아볼 것은 이진탐색 입니다.
이진탐색의 시간복잡도는 $O(logn)$으로
n의 숫자가 크면 클수록 선형탐색보다 이진탐색으로 탐색하는 것이 훨씬 효율적입니다.

✔️ 조건

이렇게 좋은 이진탐색을 사용하기 위해서는 조건이 있습니다.
그것은 탐색할 배열이 정렬된 상태여야 한다는 것 입니다.

하지만 swift 기본 정렬의 시간복잡도가 $O(nlogn)$이기 때문에
일반적인 경우에 정렬을 하고 이진탐색을 하는 것은
선형탐색을 하는 것보다 시간복잡도면에서 비효율적일 수 있습니다.

그러니 상황을 보고 사용하는 것이 좋겠습니다 ㅎㅎ

📚 원리

이진 탐색은 정렬이 되어있는 배열 기준으로 탐색을 합니다.
(배열이 오름차순으로 정렬되어 있다고 가정하고 설명하겠습니다.)

1. 배열의 시작과 끝을 start / end 변수에 저장해준다.
2. start와 end의 중간 값이 원하는 값보다 큰지 작은지 확인한다.
3. 크다면 중간 값 이후의 값들은 더이상 볼 필요가 없기 때문에
   end값에 중간값 - 1 을 저장하고, 작다면 중간 값 이전의 값을 볼 필요가 없기 때문에 중간값 + 1 을 start로 다시 설정한다.
   만약에 중간 값과 내가 원하는 값이 같다면 원하는 값을 찾은 것 이므로
   그 인덱스를 return 한다.
4. 시작 값이 끝 값보다 작거나 같아지면 탐색이 끝난 것 이므로 while문을 종료한다. -> 이렇게 종료되면 해당 배열 안에 내가 찾는 값이 없다는 의미이므로 식별할 수 있는 값을 return 해준다.
   
   
   
   

✍🏻 구현

swift

func binarySearch(_ array: [Int], num: Int) -> Int? {
    var start = 0
    var end = array.count - 1
    
    while start <= end {
        let mid = (start + end) / 2
        let guess = array[mid]
        if guess == num {
            return mid
        } else if guess > num {
            end = mid - 1
        } else {
            start = mid + 1
        }
    }
    return -1
}

python

def solution(L, x):
    start = 0
    end = len(L) - 1
    
    while start <= end :
        mid = (start + end) // 2
        guess = L[mid]
        if guess == x :
            return mid
        elif guess > x :
            end = mid - 1
        else :
            start = mid + 1
            
    return -1