二分查找

二分查找也称折半查找，它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列，二分法概念本身不难，但是细节之处确实需要大量工作。

现有一个正整数集合，[2,4,8,3,6,9,1,10,5]，使用递归二分查找找出缺失的数字。

  1. let datas = [2, 4, 8, 7, 6, 3, 1, 10, 5];
  3. let newData = datas.sort((a1, a2) => { return a1 - a2 });
  5. //shouldStart：理应开始的值，shouldEnd：理应结束的值，data：问题数组
  6. function check(shouldStart, shouldEnd, data) {
  8.     if (data[0] != shouldStart) return shouldStart; //检测起始
  9.     if (data.slice(-1) != shouldEnd) return shouldEnd;
  11.     let ShouldSum = shouldStart + shouldEnd;
  13.       //中间值
  14.     let mid = !ShouldSum % 2 ?
  15.         [ShouldSum / 2] : [(ShouldSum / 2) - 0.5, (ShouldSum / 2) + 0.5];
  18.     for (let i = 0; i < mid.length; i++) {
  19.         if (data.indexOf(mid[i]) == -1) {
  20.             return mid[i];//终止条件
  21.         }
  22.     }
  24.     let A = shouldEnd - shouldStart + 1;
  26.       //均分长度
  27.     let minLength = A % 2 ? (A / 2 - 0.5) : (A / 2 - 1);
  29.       //实际被切割的两部分数组
  30.     let left = [], right = [], theData;
  32.     if (mid.length == 2) theData = data.join(',').split(`,${mid[0]},${mid[1]},`);
  34.     else theData = data.join(',').split(`,${mid[0]},`);
  36.     if (theData[0].length != 1)
  37.         theData[0].split(',').forEach(p => left.push(parseInt(p)));
  38.     else left = theData[0];
  40.     if (theData[1].length != 1)
  41.         theData[1].split(',').forEach(p => right.push(parseInt(p)));
  42.     else right = theData[1];
  44.         //递归
  45.     if (left.length < minLength)
  46.         return check(shouldStart, shouldStart + minLength - 1, left);
  47.     if (right.length < minLength)
  48.         return check(shouldEnd - minLength + 1, shouldEnd, right);
  50. }
  52. check(1, 10, newData)

实现原理：递归二分查找。

使用二分查找前提条件是对原始数组进行排序，使用了 sort() 方法。其次找出中间值，因为数组起始位置的不同，中间值可能存在两个。 例如：1~7的连续正整数，中间值应该是4。而1~8的连续正整数，中间值应该是4和5，应该储存中间值应该是Array 类型，中间值通过4将数组均分为两部分。

二分查找的核心在于递归，而递归的结束条件应该有2个：

1、判断首尾，例如我们判断1~10的连续正整数缺失部分则先判断首尾1和10是否存在； 2、判断中间数是否存在，例如中间数为4那么判断4是否存在，中间数为4和5，那么判断4、5是否存在；

以此递归存在问题的数组部分，即可找出缺失值。 那么什么是存在问题的数组部分呢？也就是说递归的开始条件

开始时，我们通过中间值将数组均分为两部分，因为缺失了一个元素，那么两部分定有一部分的数组长度小于理应的长度，而这部分的数组则是需要递归的数组，也就是递归开始条件。

递归的完成则体现细节的复杂性的时候，我们需要按照规律计算出：中间值、理论均分长度、理论起始值。

具体见上方代码的实现方式。