读书笔记-<算法图解>

二分法

<!doctype html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta name="viewport"
          content="width=device-width, user-scalable=no, initial-scale=1.0, maximum-scale=1.0, minimum-scale=1.0">
    <meta http-equiv="X-UA-Compatible" content="ie=edge">
    <title>Document</title>
</head>
<body>
<script>
function binary_search(list,item) {
   
    //while 循环
    var low =0;
    var high =list.length-1;

    while (low<=high){
       var  mid = Math.floor((low+high)/2); //向下取整
       var  guess = list[mid];
       if(guess === item){
           return mid;
       }else if(guess > item){
           high = mid-1
       }else {
           low = mid +1;
       }
    }

    //for 循环
    var low =0;
    var high =list.length-1;
    for(var i=0;i<list.length;i++){
        console.log("执行次数---",i)
        var  mid = Math.floor((low+high)/2); //向下取整
        var guess = list[mid];
        if(guess === item){
            console.log(mid)
            break;
        }else if(guess > item){
            high = mid-1;
        }else{
            low= mid+1;
        }
    }
}

var myList = [1,2,3,4,5,6,7,8,9];

binary_search(myList,3)

</script>
</body>
</html>


递归


    var total = 0;

    function sum(arr) {
        total += arr.shift();
        if (arr.length > 0) {
            sum(arr)
        } else {
            console.log(total);
        }
    }

    var list = [1, 2, 3]
    sum(list)


    var length=0;
    function findLength(list) {
        if(list.length>0){
            length+=1;
            list.shift();
            findLength(list)
        }else{
            console.log(length)
        }
    }
    var list = [1, 2, 3]
    findLength(list)

快速排序

function quickSort(array) {
    if(array.length<2){
        console.log("zhixingle <2")
        return array
    }else{
        var pivot = array[0];
        var less = []; //小于基准线的小数组
        var greater =[]; // 大于基准线的大数组
        
        for(var i=1;i<array.length;i++){
            if(array[i]<pivot){
                less.push(array[i])
            }else{
                greater.push(array[i])
            }
        }
        return quickSort(less).concat(pivot,quickSort(greater))
    }
}

console.log(quickSort([5,4,3,2,1]))