在js中我们常常会遇到这样的问题,在一个数组中找到目标值的位置。当这个数组很小的时候很简单,直接for循环遍历,把目标值和遍历值对比,如果相等,就返回此时遍历的下标 i。
但是数组如果很大,这样的方法查询效率会很慢,有木有更好方法呢? 当然有,在下提供一个方法, 二分搜索法。也称折半搜索,是一种在有序数组中查找特定元素的搜索算法。
实现思路:
1. 首先从数组中间开始查找对比,若相等则找到,直接返回中间元素的索引。
2. 若查找值小于中间值,则在小于中间值的那一部分执行步骤1的操作。
3. 若查找值大于中间值,则在大于中间值的那一部分执行步骤1的操作。
4. 否则,返回结果为查不到,返回-1。
function binary_search1(arr, val) {
var low = 0;
var high = arr.length - 1;
while(low <= high) {
var mid = parseInt((low + high) / 2);
if(val === arr[mid]) {
return mid;
}
else if(val < arr[mid]) {
high = mid + 1;
}
else if(val > arr[mid]) {
low = mid - 1;
}
else {
return-1;
}
}
}
var arr = [1,2,3,4,5,6,7,8,9,10,11,12];
console.log(binary_search1(arr, 3));
网友评论