| JavaScript, 算法

算法之有序数组搜索方法

1. 分治和递归

  1. 分治法
    a. 将问题的规模变小；
    b. 递归处理小规模问题；
    c. 将小规模问题的解合并为原始问题的解。

  2. 递归的要点
    a. 终止条件是什么（最小子问题是怎么求解的）；
    b. 需要保证问题规模是在向终止条件靠拢。

2. 有序数组的搜索方法

  1. 二分查找来搜索
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    // 二分查找
           let arr = [1,3,5,7,8,9,10];
           function indexOf(arr,key){
               let len = arr.length;
               if(len === 0){   // 需要一个终止的条件
                   return -1;
               }
               let i = Math.floor(len / 2);
               if(arr[i] === key){
                   return i;
               }
    		// 在这里问题规模就是数组的大小，因此我们需要保证arr.slice()让数组的大小一直是在减小的；
    		// 如果数组的大小一直保持不变的话，就会造成递归的死循环，最后导致堆栈溢出。
               if(key < arr[i]){
                   return indexOf(arr.slice(0,i),key);
               }else{
                   let result = indexOf(arr.slice(i+1),key);
                   return result === -1 ? result : i + 1 + result;
               }
           }
           console.log(indexOf(arr,11));   // -1
           console.log(indexOf(arr,5));   // 2
           console.log(indexOf(arr,7));   // 3
           console.log(indexOf(arr,9));   // 5
    下面这种方法可以让递归的次数再少一点（细节优化）：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    // 二分查找
           let arr = [1,3,5,7,8,9,10];
           function indexOf(arr,key){
               let len = arr.length;
               let i = Math.floor(len / 2);
               if(arr[i] === key){
                   return i;
               }
               // arr[i] ===key的条件放在前面，表示它的长度只有一个，
               // 但是和我们搜索的条件是不想等的
               if(len === 1){
                   return -1;
               }
    		// 在这里问题规模就是数组的大小，因此我们需要保证arr.slice()让数组的大小一直是在减小的；
    		// 如果数组的大小一直保持不变的话，就会造成递归的死循环，最后导致堆栈溢出。
               if(key < arr[i]){
                   return indexOf(arr.slice(0,i),key);
               }else{
                   let result = indexOf(arr.slice(i+1),key);
                   return result === -1 ? result : i + 1 + result;
               }
           }
           console.log(indexOf(arr,11));   // -1
           console.log(indexOf(arr,5));   // 2
           console.log(indexOf(arr,7));   // 3
           console.log(indexOf(arr,9));   // 5