2. Binary Search

Binary Search

Binary Search는 오름차순으로 정렬된 데이터의 배열에서 원하는 값을 찾는 알고리즘

배열 중간의 임의의 값을 선택하고 원하는 값을 비교하여 원하는 값이 중간 값보다 작으면 좌측 데이터의 중심 다시 데이터 값을 비교하고 원하는 값이 중간 값보다 크면 우측 데이터 중심에서 값을 비교하는 것을 반복하여 값을 찾는 과정

검색 원리상 정렬된 리스트에만 사용할 수 있다는 단점이 있으나 검색이 반복될 때마다 목푯값을 찾을 확률은 두 배가 되므로 속도가 빠르다는 장점

let numbers = [1, 2, 4, 6, 8, 9, 11, 13, 16, 17, 20]
var hundred = [Int]()
for i in 1...100 {
    hundred.append(i)
}

func binarySearchForSearchValue(searchValue : Int, array : [Int]) -> Bool {
    
    var leftIndex = 0
    var rightIndex = array.count - 1
    
    while leftIndex <= rightIndex {
        
        let middleIndex = (leftIndex + rightIndex) / 2
        let middleValue = array[middleIndex]
   
        print("middleValue : \(middleValue), leftIndex : \(leftIndex), rightIndex : \(rightIndex), [\(array[leftIndex]), \(array[rightIndex])]")
        if middleValue == searchValue {
            return true
        }
        if searchValue < middleValue {
            rightIndex = middleIndex - 1
        }
    
        if searchValue > middleValue {
            leftIndex =  middleIndex + 1
        }
    }
    return false
}

print(binarySearchForSearchValue(searchValue: 99, array: hundred))