Fork me on GitHub

二分查找法

发表于 | 分类于

二分查找法

二分查找法也称折半查找法，适用于在已知排列顺序的有序数组查找某个特定元素。

原理：

(1)首先，从数组的中间位置开始查找。如果要查找的元素等于中间元素，返回中间元素索引。否则，进行第二步。

(2)如果要查找的元素大于中间元素，则在数组大于中间元素的那半区域进行查找；

如果要查找的元素小于中间元素，则在数组小于中间元素的那半区域进行查找。

然后重复第一步的操作。

(3)如果要查找的元素不存在，则返回-1。

具体实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function search (data, target) {
    var start = 0,
        end = data.length - 1;
    while (start <= end) {
        var middle = Math.floor((start + end) / 2);     //找到中间元素
        if (target === data[middle]) {
            return middle;
        }else if (target > data[middle]) {
            start = middle + 1;
        }else {
            end = middle - 1;
        }
    }
    return -1;     //要查找的元素不存在
}

var arr = [1, 5, 2, 7, 13, 2, 3, 4, 34];
var result = search(arr, 7);   //方法调用
console.log(result);    //3,返回目标元素的索引