Binary Search

二元搜寻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