Binary Search

Binary Search(이분탐색)

• 데이터의 중간값을 확인하면서 탐색하는 기법
• 데이터가 정렬 되있을 때 효과적
• 시간 복잡도는 O(logN)

func binarySearch(list: [Int], element: Int) -> Int? {
    var firstIndex = 0
    var lastIndex = list.count - 1
    
    while firstIndex <= lastIndex {
        let midIndex = (firstIndex + lastIndex) / 2
        
        if list[midIndex] < element {
            firstIndex = midIndex + 1
        } else if list[midIndex] > element {
            lastIndex = midIndex - 1
        } else {
            return midIndex
        }
    }
    
    return nil
}

binarySearch(list: [1, 3, 4, 5, 6, 7, 9], element: 7) // Optional(5)
binarySearch(list: [1, 3, 4, 5, 6, 7, 9], element: 8) // nil