이진탐색 - Swift

이진탐색 

데이터가 정렬 되어있는 상황에서 특정 요소를 효율적으로 탐색하는 방법입니다.

오름차순으로 정렬 되어있는 A 배열 [1, 2, 3, 4, 5, 6, 7] 이 있습니다. 저희는 6을 찾고 싶습니다.

만약 선형탐색이라면 1 거치고 2 거치고 해서 6까지 가야하기 때문에 6번을 거쳐야 합니다. O(n)

이진 탐색을 이용한다면 3번만 거치면 6을 찾을 수 있습니다. O(logN)

이진 탐색 한번 거쳤을 때

이진 탐색을 두번 거쳤을 때

 

이진 탐색을 세번 거쳤을 때

구현 방법

1. 이진 탐색을 구현하는 방법은 주어진 배열의 첫번째 인덱스와 마지막 인덱스를 변수로 선언합니다.
2. 마지막 인덱스를 2로 나워 Mid 변수로 선언합니다.
3. Mid 인덱스에 위치하고 있는 value 값과 찾으려는 element 크기를 비교합니다.
4. Mid 값 > 찾으려는 값 이면 마지막 인덱스를 Mid - 1 값으로 초기화 합니다.
5. Mid 값 < 찾으려는 값 이면 마지막 인덱스를 Mid +1 1 값으로 초기화 합니다.
6. 찾으려는 값을 만날 때 까지 1~5 반복합니다.

 

코드

let arr = [1, 2, 3, 4, 5, 6, 7]

func binarySearch(_ element: Int) -> Bool {
    var left = 0
    var right = n - 1
    
    while left <= right {
        let mid = (left+right) / 2
        let value = arr[mid]
        
        if value == element {
            return true
        } else if value > element {
            right = mid - 1
        } else {
            left = mid + 1
        }
    }
    
    return false
}