javascript算法系列（第二周）：二分法

二分法查找，也称为折半法，是一种在有序数组中查找特定元素的搜索算法。

二分法查找的思路如下：

（1）首先，从数组的中间元素开始搜索，如果该元素正好是目标元素，则搜索过程结束，否则执行下一步。

（2）如果目标元素大于/小于中间元素，则在数组大于/小于中间元素的那一半区域查找，然后重复步骤（1）的操作。

（3）如果某一步数组为空，则表示找不到目标元素。

二分法查找的时间复杂度O(logn)

两个指针： left 和 right。 根据left和right确定mid位置。通过对目标值和mid位置的值进行对比，得出目标值位于left与mid区间还是mid与right区间，进而移动left或者right指针，重复上述步骤

二分法的前提是 数组是有序数组。

js有内置的indexOf函数，用于查找某一特定元素，该函数的时间复杂度是O(n)。为什么不用二分查找呢，因为二分查找的前提是要是有序数列，而排序的过程也是一个耗时的过程，虽然二分查找可以大大提高查找效率，但对于有限个数组意义不大。

javascript代码：

const fn = （arr, num）=> {
	let l = 0
    let r = arr.length - 1
    while (l <= r) {
        const mid = Math.floor((l + r) / 2)
        if (arr[mid] === num) {
            return mid
        } else if (arr[mid] < num) {
            l = mid + 1
        } else {
            r = mid - 1
        }
    }
    return -1
}

let arr = [1,2,3,4,5,6,7,8,9]
let num = 6
console.log(fn(arr, num));  // 5

python代码：

def binary_search(li, val):
	left = 0
	right = len(li) -1
	while left <= right:
		mid = (left + right) // 2
		if (li[mid] === val):
			return mid
		elif li[mid] > val:
			right = mid - 1
		else:
			left = mid + 1
	else:
		return None

最后

以上就是风趣方盒为你收集整理的javascript算法系列（第二周）：二分法的全部内容，希望文章能够帮你解决javascript算法系列（第二周）：二分法所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。