本帖最后由 loulansd 于 2021-5-8 12:27 编辑
假设要在电话簿中找一个名字以K打头的人，（现在谁还用电话簿！）可以从头开始翻页，直到进入以K打头的部分。但你很可能不这样做，而是从中间开始，因为你知道以K打头的名字在电话簿中间。又假设要在字典中找一个以O打头的单词，你也将从中间附近开始。现在假设你登录Facebook。当你这样做时， Facebook必须核实你是否有其网站的账户，因此必须在其数据库中查找你的用户名。如果你的用户名为karlmageddon， Facebook可从以A打头的部分开始查找，但更合乎逻辑的做法是从中间开始查找。这是一个查找问题，在前述所有情况下，都可使用同一种算法来解决问题，这种算法就是二分查找。
二分查找是一种算法你可以用你熟悉的任何一门语言实现，其输入是一个有序（大小顺序排列好的）的元素列表。如果要查找的元素包含在列表中，二分查找返回其位置（数组索引号）。
我随便想一个1～100的数字。
你的目标是以最少的次数猜到这个数字。你每次猜测后，我会说小了、大了或对了。
假设你从1开始依次往上猜，猜测过程会是这样。
0.png (83.73 KB, 下载次数: 0)下载附件2 小时前 上传
更佳的查找方式：
直接从50开始查找，如果小了，但排除了一半的数字！至此，你知道1～50都小了。
接下来，你猜75大了， 那余下的数字又排除了一半！使用二分查找时，你猜测的是中间的数字，从而每次都将余下的数字排除一半。接下来，你猜63（ 50和75中间的数字）......
这就是二分查找，你学习了第一种算法！
不管我心里想的是哪个数字，你在7次之内都能猜到，因为每次猜测都将排除很多数字！假设你要在字典中查找一个单词，而该字典包含240 000个单词，你认为每种查找最多需要多少步？如果要查找的单词位于字典末尾，使用简单查找将需要240 000步。使用二分查找时，每次排除一半单词，直到最后只剩下一个单词。
接下来用代码实现：
[JavaScript] 纯文本查看 复制代码 function binary_search(arr, key) {
var low = 0,
high = arr.length - 1;
while(low <= high){
var mid = parseInt((high + low) / 2);
if(key == arr[mid]){
return mid;
}else if(key > arr[mid]){
low = mid + 1;
}else if(key < arr[mid]){
high = mid -1;
}
}
return -1;
};
var arr = [1,2,3,4,5,6,7,8,9,10,11,56,57,60];
console.log(arr.length);
var result = binary_search(arr,11);
alert(result); // 返回目标元素的索引值
1.定义了一个函数binary_search其中的形参arr是一组有序的数据，key是你需要查找的数字。
2.声明了两个变量low（用于表示折半数组索引号第一个数）和high（数组的元素长度减1就是14-1=13）如果low <= high那么就会执行low和high相加除二并取整数，就是得到了6并赋值给变量mid。
3.比较是否与key（你需要查找的数字）相等
4.如果不相等的话会继续判断是大了还是小了。如果key的值比猜到的值大那么，就会执行
low = mid + 1;
执行完后这时low就变为7，high不变，这时就判断数组索引号07（low）到13（high）的数字
5.一次反复运算最后key == arr[mid]成立的时候就返回值，最后弹窗输出需要查找的数的索引号。
使用它可节省多少时间呢？简单查找逐个地检查数字，如果列表包含100个数字，最多需要猜100次。如果列表包含40亿个数字，最多需要猜40亿次。换言之，最多需要猜测的次数与列表长度相同，这被称为线性时间
（linear time）。二分查找则不同。如果列表包含100个元素，最多要猜7次；如果列表包含40亿个数字，最多需猜32次。厉害吧
参考书籍：算法图解 by [美] Aditya Bhargava
论坛有分享：《算法图解》（pdf）非扫描版 - 『电子书屋』 - 吾爱破解 - LCG - LSG |安卓破解|病毒分析|www.52pojie.cn
个人理解分享，如有错误欢迎指正。 | 
[复制链接]
发表于 2021-5-7 21:08
|
发表于 2021-5-8 13:42
