Binary Search 이진탐색

이진탐색

- 배열에서 원하는 원소를 찾는 탐색 방법이다.
- 이미 정렬이 되어있는 상태에서만 사용할 수 있다.
- 반씩 끊어가며 찾는 방법으로 O(logN) 의 시간복잡도를 갖는다.

 

---

 

이진 탐색은 이미 정렬이 되어있는 배열에서 원하는 원소를 효율적으로 찾을 수 있는 알고리즘입니다.

원리는 간단합니다.

 

이미 정렬이 되어있는 상태이기 때문에 반을 뚝 짤라서 찾는 원소가 왼쪽인지 오른쪽인지 확인해 아닌 부분은 버립니다.

 

조금 더 살펴보면, 시작 부분을 low, 끝 부분을 high라고 해볼게요. 

array = [1, 5, 7, 15, 22, 65, 80, 100] 배열이 이런식으로 있고 65를 찾고 싶다면, 

시작할 때 low = 0, hight = 6 (array.count-1) 이고 mid = 3 = (0 + 6) / 2 이 됩니다.

mid를 찾았으니 타겟이 mid보다 큰지 작은지 확인해서 low 또는 high의 값을 변경해줍니다.

확인해보면 arr[mid] = 15 < 65 이므로 65는 mid인 15보다 오른쪽에 있다는 것을 알 수 있습니다.

따라서 low = mid+1 해서 low를 미드보다 하나 오른쪽으로 옮겨주는거에요. 

이런 식으로 반복해가면 한번 확인할 때마다 절반씩 줄여나갈 수 있으므로 O(logN) 만에 탐색을 끝낼 수 있습니다.

 

코드를 살펴볼게요.

func binarySearch(arr: [Int], target: Int) -> Int? {
    var low = 0
    var high = arr.count-1

    while low <= high {
        let mid = (low + high)/2

        if arr[mid] == target {
            return mid
        } else if target < arr[mid] {
            high = mid-1
        } else {
            low = mid+1
        }
    }
    return nil
}

 

재귀적으로도 풀 수 있습니다.

func binarySearchRecurse(_ arr: [Int], _ target: Int, from low: Int, to high: Int) -> Int? {
    guard low < high else { return nil }
    
    let mid = (low + high)/2
    
    if arr[mid] == target {
        return mid
    } else if target < arr[mid] {
        return binarySearchRecurse(arr, target, from: low, to: mid-1)
    } else {
        return binarySearchRecurse(arr, target, from: mid+1, to: high)
    }
}

 

 

감사합니다 !