04. 查找算法

一、二分查找算法：

一、是什么

在计算机科学中，二分查找算法，也称折半搜索算法，是一种在有序数组中查找某一特定元素的搜索算法

想要应用二分查找法，则这一堆数应有如下特性：

• 存储在数组中
• 有序排序

搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束

如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较

如果在某一步骤数组为空，则代表找不到

这种搜索算法每一次比较都使搜索范围缩小一半

如下图所示：

相比普通的顺序查找，除了数据量很少的情况下，二分查找会比顺序查找更快，区别如下所示：

二、代码实现

基于二分查找的实现，如果数据是有序的，并且不存在重复项，实现代码如下：

// 二分法。
function BinarySearch(arr, value) {
	if (arr === null || !arr.length) return -1;
	// 开始、结束下标。
	let start = 0, end = arr.length - 1;

	while (start <= end) {
		// 中间下标。
		const midIndex = Math.floor((end + start) / 2);
		if (value < arr[midIndex]) {
			end = midIndex - 1;
		} else if (value > arr[midIndex]) {
			start = midIndex + 1;
		} else {
			return midIndex;
		};
	};

	return -1;
};

如果数组中存在重复项，而我们需要找出第一个制定的值，实现则如下：

function BinarySearchFirst(arr, target) {
    if (arr.length <= 1) return -1
    // 低位下标
    let lowIndex = 0
    // 高位下标
    let highIndex = arr.length - 1

    while (lowIndex <= highIndex) {
        // 中间下标
        const midIndex = Math.floor((lowIndex + highIndex) / 2)
        if (target < arr[midIndex]) {
            highIndex = midIndex - 1
        } else if (target > arr[midIndex]) {
            lowIndex = midIndex + 1
        } else {
            // 当 target 与 arr[midIndex] 相等的时候，如果 midIndex 为0或者前一个数比 target 小那么就找到了第一个等于给定值的元素，直接返回
            if (midIndex === 0 || arr[midIndex - 1] < target) return midIndex
            // 否则高位下标为中间下标减1，继续查找
            highIndex = midIndex - 1
        }
    }
    return -1
}

三、应用场景

二分查找法的O(logn)让它成为十分高效的算法。不过它的缺陷却也是比较明显，就在它的限定之上：

• 有序：我们很难保证我们的数组都是有序的
• 数组：数组读取效率是O(1)，可是它的插入和删除某个元素的效率却是O(n)，并且数组的存储是需要连续的内存空间，不适合大数据的情况

关于二分查找的应用场景：

• 不适合数据量太小的数列；数列太小，直接顺序遍历说不定更快，也更简单
• 每次元素与元素的比较是比较耗时的，这个比较操作耗时占整个遍历算法时间的大部分，那么使用二分查找就能有效减少元素比较的次数。