Shellway

JS二分查找算法示例

简介

二分查找又称折半查找,优点是比较次数少,查找速度快,平均性能好;其缺点是要求待查表为有序表,且插入删除困难。因此,折半查找方法适用于不经常变动而查找频繁的有序列表。首先,假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功;否则利用中间位置记录将表分成前、后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表。重复以上过程,直到找到满足条件的记录,使查找成功,或直到子表不存在为止,此时查找不成功。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
var Arr = [3, 5, 6, 7, 9, 12, 15];
function binary(find, arr, low, high) {
if(low <= high) {
if(arr[low] == find) return low;
if(arr[high] == find) return high;
var mid = Math.ceil((high + low) / 2);
if(arr[mid] == find) {
returnmid;
}
elseif (arr[mid] > find) {
return binary(find, arr, low, mid - 1);
} else {
returnbinary(find, arr, mid + 1, high);
}
}
return -1;
}
binary(15, Arr, 0, Arr.length - 1);