前言
在开发中我们经常会听到"分治法"、“二分思想”的理念，而二分查找就是该理念的经典实现。
经典面试题：在一个有序数组中如何快速的查找目标为n的元素索引位置，不存在则返回-1。
小白式算法实现
尤其是面试时，当面试官问到这样一个问题，小白式的同学感觉会特别简单，遍历一遍进行比对不就OK了，今天真是中奖了，这么简单~~
No Use Think! Up Code! (不用想！上代码！)
/** * @method forSearch * @description 使用for循环查询 * @param nums number[] * @param target number * @returns number */ function forSearch(nums: number[], target: number): number { // 数组长度 const len = nums.length; // 临界值判断 if (len === 0) { return -1; } for (let i = 0; i < len; i++) { if (nums[i] === target) { return i; } } return -1; }
以上实现算法复杂度：
- 空间复杂度 O(n)O(n)O(n)
- 时间复杂度 O(n)O(n)O(n)
一般当你写出这个答案的时候，面试官内心肯定会嘿嘿一笑，这不又入坑一个。接下来就会“贱贱”的提出下一个问题，有没有更优的算法实现，复杂度降低到
O(logn)O(logn)O(logn)。
低于O(n)O(n)O(n)时间复杂度的实现有没有？
一般当你看到复杂度O(logn)O(logn)O(logn)的时候，一定要有算法的敏感性，这个就是要本着二分法去的~
二分法有个必然的前提是数组必须是有序的！升序和降序无所谓。
二分法是什么原理呢，假定当前nums是一个包含数字的升序数组。每次取数组中的12{\frac 1 2}21位置的值midValue，与目标值target进行比对：
- 若
midValue>target值，说明与target匹配的值是在左边，接下来再取左侧的12{\frac 1 2}21位置的数据进行比对；
- 若
midValue<target值，说明与target匹配的值是在右边，接下来再取右侧的12{\frac 1 2}21位置的数据进行比对；
- 若
midValue===target值，返回对应位置索引；
- 若最终比对没有符合目标值的，返回 -1
根据这个逻辑，上代码看一看~
/** * @method binarySearch * @description 基于二分法实现查询 - 函数递归 * @param nums number[] * @param target number * @param startIndex number 表示开始比对的左侧索引开始位置 * @param endIndex number 表示开始比对的右侧索引结束位置 * @returns */ function binarySearch( nums: number[], target: number, startIndex?: number, endIndex?: number ): number { // 获取数组 const len = nums.length; // 临街值判断 if (len === 0) { return -1; } // 在初始值情况下，对startIndex和endIndex进行初始化赋值 if (startIndex === undefined) { // 索引0开始 startIndex = 0; } if (endIndex === undefined) { // 最后一个索引位置结束 endIndex = len - 1; } // 判断startIndex和endIndex是否已经交叉，若交叉说明没有匹配的结果 if (startIndex > endIndex) return -1; // 获取当前startIndex和endIndex的二分之一位置 const midIndex = Math.floor((startIndex + endIndex) / 2); // 向下取整，避免奇偶数长度问题 // 二分之一位置的值 const midValue = nums[midIndex]; if (midValue > target) { // 在左侧，将结束索引位置，移动到 midIndex - 1 return binarySearch2(nums, target, startIndex, midIndex - 1); } else if (midValue < target) { // 在右侧，将开始索引位置，移动到 midIndex + 1 return binarySearch2(nums, target, midIndex + 1, endIndex); } else { // 匹配返回索引 return midIndex; } }
二分法查找，每次都在进行二分之一处理的时候，都是在逼近最终的结果，其时间复杂度为O(logn)O(logn)O(logn)。
对比下两个方案的性能：选取一个1W条数据的数组，查询999，每个查询都执行了10W次。
// 声明数组nums const nums = []; for (let i = 0; i < 10000; i++) { nums.push(i); } // 设置target const target = 999; // for循环的实现 console.time('forSearch'); for (let i = 0; i < 10 * 10000; i++) { forSearch(nums, target); } console.timeEnd('forSearch'); // 二分查找实现 console.time('binarySearch'); for (let i = 0; i < 10 * 10000; i++) { binarySearch(nums, target); } console.timeEnd('binarySearch');
有图有真相，二者时间消耗对比还是非常明显的，O(log(n))O(log(n))O(log(n))复杂度要远胜于O(n)O(n)O(n)复杂度的。
注：大家在看算法复杂度时，一定要注意有最好情况时间复杂度、最坏情况时间复杂度、平均时间复杂度、均摊时间复杂度。
方案一 - 循环查询，最好的时间复杂度就是O(1)O(1)O(1)，第一个找的元素就是。最坏的时间复杂度是O(n)O(n)O(n)，最后一个元素才是。
方案二 - 二分查询，最好时间复杂度是O(1)O(1)O(1)，恰好查询的元素是二分之一位置的，最坏的是O(logn)O(logn)O(logn)，最边上的元素是目标元素。
而且复杂度讨论的是量级问题，而并不是一个时间损耗绝对值的问题。
