(以下资料来自百度百科)
查找过程：
首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。
算法要求：
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);
网友评论