二元搜尋BigO(log n)

• 相較於線性搜尋時間複雜度實在好太多
• 必須是被排序好的
• 由於每次對半砍,所以為log n

點我看GIF

let array1 = [1,3,5,7,9,11,13,15,17,19,21]

function BinarySearch(array, n){
    let min = 0
    let max = array.length -1 

    while(array[min] <= array[max]){ //當array的前一項比後項小即成立
        let middile = Math.floor((min + max) / 2) //為了對半middle 為中間的index

        if(array[middile] > n){ //如果array[middle] > n 代表是在miidle的左半邊,即把範圍所小到當前middle的位置-1
            max = middile - 1
        }else if(array[middile] < n ){
            min = middile + 1
        }else{ //否則回傳middle
            console.log(`Found number index:${middile}`)
            return middile
        }
    }return "Error"
}
BinarySearch(array1, 5) //Found number index:2