<html lang="en-US">
<head>
<meta charset="UTF-8">
<meta name="keywords" content="白菜编辑部">
<title>白菜编辑部</title>
<style type="text/css">
</style>
<script type="text/javascript">
function binarySearch0 (a, fromIndex, toIndex, key)
{
var low = fromIndex
var high = toIndex - 1
while (low <= high)
{
var mid = (low + high) >>> 1
var midVal = a[mid]
if (midVal < key)
{
low = mid + 1
}
else if (midVal > key)
{
high = mid - 1
}
else
{
return mid // key found
}
}
return -(low + 1) // key not found.
}
function binarySearch (a, key)
{
return binarySearch0 (a, 0, a.length, key)
}
var arr = [
1, 4, 6, 8, 9, 90, 800
]
console.log (binarySearch (arr, 90))
</script>
</head>
<body>
</body>
</html>
二分查找算法，该算法要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。如果一个序列是无序的或者是链表，那么该序列就不能使用二分查找。
二分查找算法原理：若待查序列为空，则返回-1，并退出算法；若待查序列不为空，则将它的中间元素与目标数值进行比较，判断是否相等；若相等，则返回中间元素索引，并退出算法；此时已查找成功。若不相等，则比较中间元素与目标数值的大小。
若中间元素>目标数值，则将当前序列的前半部分作为新的待查序列；若中间元素<目标数值，则将当前序列的后半部分作为新的待查序列；在新的序列上重新从第（1）步开始查找。
二分法查找的思路：首先，从数组的中间元素开始搜索，如果该元素是目标元素，则搜索过程结束，否则执行下一步。如果目标元素大于/小于中间元素，则在数组大于/小于中间元素的那一半区域查找，然后重复步骤（1）的操作。如果某一步数组为空，则表示找不到目标元素。
二分查找的一个技巧是：不要出现else，而是把所有情况用else，if写清楚，这样可以清楚地展现所有细节。本文都会使用else，if，旨在讲清楚，读者理解后可自行简化。
通过线性查找检索出现在视口内的元素，效率较低 比如 js寻找在视口内的元素-线性查找 对100个元素进行查找，需要循环100次，或者找到之后跳出循环。通过二分查找改进，先找到一个出现在视口内的元素，再从它的上下查找。
码
