1、线性查找

数组中查找数据的算法， 比如从数组中找到某个值 ，复杂度为O(n), 思想是，从左开始循环，遇到这个数便停止查找

  1. let num = 8;
  2. let arr = [1,2,3,4,5,6,7,8,9,0]
  3. function findNum(arr,num){
  4.     let result = {
  5.        num: null,
  6.        index: null
  7.     }
  8.     for(let i =0;i<arr.length; i++){
  9.        if(arr[i] === num){
  10.           result.num = num;
  11.           result.index = i
  12.           break;
  13.        }
  14.     }
  15.    return result
  16. }
  17. console.log(findNum(arr,num))

2、二分查找

二分查找与线性查找不同的是，需要先进行排序，然后与中间数比较，进行二分，直到最终找到目标 二分查找因为每次范围减半，复杂度为O(logn) , 比线性更快，但是要求是必须顺序排列，而且插入数据时不如线性方便

  1. let arr = [1, 2, 6, 3, 8, 2, 0, 5, 7];
  2. let num = 2;
  3. function findNum(arr, findNum) {
  4.   let cloneArr = JSON.parse(JSON.stringify(arr));
  5.   let result = {
  6.     num: null,
  7.     index: null,
  8.   };
  10.   // 考虑边界
  11.   if (findNum > Math.max(...arr) || findNum < Math.min(...arr)) return result;
  12.   // 先排序
  13.   function findValue(arr, findNum) {
  14.     // 在中间的时候
  15.     let midIndex = Math.floor(arr.length / 2);
  16.     let midValue = arr[midIndex];
  17.     let n;
  18.     if (findNum > midValue) {
  19.       n = findValue(arr.slice(midIndex), findNum);
  20.     } else if (findNum < midValue) {
  21.       n = findValue(arr.slice(0, midIndex), findNum);
  22.     } else if (findNum === midValue) {
  23.       n = findNum;
  24.     }
  25.     return n;
  26.   }
  27.   arr = arr.sort((a, b) => a - b);
  28.   let n = findValue(arr, findNum);
  29.   result.index = cloneArr.findIndex((el) => el === n);
  30.   result.num = n;
  31.   return result;
  32. }
  33. console.log(findNum(arr, num));