面试 - js 二分法，二分查找

记录二分法

二分法

二分查找是一种高效搜索法，是一种可以在有序数组中搜索到特定元素的算法

优缺点

• 优：比较次数少，查找速度快，平均性能好，
• 缺: 要求待查表为有序表，且插入删除困难，

 const arr = [2, 1, 3, 5, 6, 4, 7];

 function bubbleSort(arr) {
   if (!arr.length) return arr;
   const copyArr = arr.slice();
   for (let i = 0, length = copyArr.length; i < length; i++) {
     for (let j = 0; j < length - i - 1; j++) {
       const current = copyArr[j];
       const next = copyArr[j + 1];
       if (current > next) [copyArr[j], copyArr[j + 1]] = [next, current]
     }
   }
   return copyArr;
 }
 
 const sortArr = bubbleSort(arr);

// 递归
 function binarySearch(arr, num, low = 0, height = arr.length || 0) {
   const midIndex = Math.floor((low + height) / 2)
   const midNum = arr[midIndex];
   if (midNum === num) return [midIndex, midNum];
   if (midNum > num) {
     height = midIndex - 1;
     return binarySearch(arr, num, low, height);
   }
   if (midNum < num) {
     low = midIndex + 1;
     return binarySearch(arr, num, low, height);
   }
 }
 
 // while
 function binarySearch1(arr, num) {
   let start = 0, end = arr.length, midNum, midIndex;

   while (start <= end) {
     midIndex = Math.floor((start + end) / 2);
     midNum = arr[midIndex];
     if (midNum === num) return {midNum, midIndex}
     if (midNum > num) end = midIndex - 1;
     else if (midNum < num) start = midIndex + 1
   }
 }

 binarySearch1(sortArr, 3)