이분탐색 Swift

이분탐색

유명한 이분탐색 이미지다.

위와 같이 완전탐색과 다르게 이분탐색은 훨씬 빠르게 데이터를 찾을 수 있다.

 

-> 이분탐색은 정렬된 리스트안에서 탐색범위를 절반씩 좁혀가며 데이터를 찾는 방식이다.

-> 배열의 내부가 정렬되어있어야 사용가능하다.

-> 세가지 변수 (start, end, target) 을 사용하며, 반복적 또는 재귀호출로 데이터를 찾는다.

재귀 호출을 이용한 이분탐색

import Foundation
// 이분탐색
func binarySearch(arr: [Int], start: Int, end: Int, target: Int) -> Int {
	// startIndex 가 endIndex를 넘으면 종료
    if start > end { return -1 }
    let mid = (start + end) / 2
    
    if arr[mid] == target {
        return mid		// 타겟을 찾으면 종료
    } else if arr[mid] > target {
    	// 중간에 위치한 값이 타겟보다 크면 값을 낮추기위해, endIndex를 옮긴다.
        return binarySearch(arr: arr, start: start, end: mid-1, target: target)
    }else {
        // 중간에 위치한 값이 타겟보다 작으면 값을 높이기위해, startIndex를 옮긴다.
        return binarySearch(arr: arr, start: mid+1, end: end, target: target)
    }
}

var a = [1, 3, 4, 5, 7, 8]
print(binarySearch(arr: a, start: 0, end: a.endIndex - 1, target: 3))
// 1

 

반복문을 이용한 이분탐색

import Foundation

func binarySearch(arr: [Int], start: Int, end: Int, target: Int) -> Int {
    var result = -1
    var startIndex = start
    var endIndex = end
    // 이분 탐색
    while startIndex <= endIndex {
        let midIndex = (startIndex + endIndex) / 2
        // 타겟을 찾으면 탈출
        if arr[midIndex] == target {
            result = midIndex
            break
        } else if arr[midIndex] > target {
            // 타겟보다 큰경우 endIndex를 줄여 mid를 작게한다
            endIndex = midIndex - 1
        } else {
            // 타겟보다 작은경우 startIndex를 늘려 mid를 크게갖는다
            startIndex = midIndex + 1
        }
    }
    return result
}

var a = [1, 3, 4, 5, 7, 8]
print(binarySearch(arr: a, start: 0, end: a.endIndex - 1, target: 8))
// 5

 

위 두가지 방법은 모두 "중복이 없는, 정렬된(오름,내림)" 리스트에서 원하는 데이터를 찾은것이다.