算法学习-查找-二分查找

(以下资料来自百度百科)

查找过程：

    首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。

算法要求：

    1.必须采用顺序存储结构。

    2.必须按关键字大小有序排列。

比较次数:

    计算公式 a<log2(n)<b(a, b, n 都是正整数), 当顺序表有n个关键字时,查找失败时，至少比较a次关键字；查找成功时，最多比较关键字次数是b。

算法复杂度:

    二分查找的基本思想是将n个元素分成大致相等的两部分，取a[n/2]与x做比较，如果x=a[n/2],则找到x,算法中止；如果xa[n/2],则只要在数组a的右半部搜索x.时间复杂度可以表示O(h)=O(log2n)

补充：

    折半查找法也称为二分查找法，它充分利用了元素间的次序关系，采用分治策略，可在最坏的情况下用O(log n)完成搜索任务。

javaScript用例：

const Arr = [3, 5, 6, 7, 9, 12, 15];

let index = -1, n = 0

function binary(find, arr, low, high) {

  n++

  if (low <= high) {

    if (arr[low] == find) {

      index = low;

      return {index, n};

    }

    if (arr[high] == find) {

      index = high;

      return {index, n};

    }

    let mid = Math.ceil((high + low) / 2);

    if (arr[mid] == find) {

      index = mid

      return {index, n};

    } else if (arr[mid] > find) {

      return binary(find, arr, low, mid - 1);

    } else {

      return binary(find, arr, mid + 1, high);

    }

  }

  return {index, n};

}

binary(9, Arr, 0, Arr.length - 1);