二分查找法

二分查找法是非常经典的一种查找法，每个程序员都应该理解并熟练掌握。

1. 算法使用前提：数组是有序数组,且无重复元素

2. 基本原理：

首先将要查找的元素(key)与数组的中间元素比较

1、如果key小于中间元素，只需要在数组的前一半元素中继续查找

2、如果key和中间元素相等，匹配成功，查找结束

3、如果key大于中间元素，只需要在数组的后一半元素中继续查找

3. 复杂度：时间复杂度O(logn)；循环实现空间复杂度为O(1)

运行速度O(1)<O(logn)<O(n)<O(nlogn)<O(n²)<O(n³)<O(2ⁿ)<O(n!)

4. 过程图示：

假如我们使用二分查找法找5

1、首先定义头尾指针，算出中间指针。本文中间数算法是向下取整mid=(start+end)/2|0。位运算|0作用是向下取整。

所有的按位操作符的操作数都会被转成补码形式的有符号32位整数。也就是如果有小数则忽略。而0 转为二进制则为 000000......(32位) 。然后一一比较，还是原来上面的值。所以只是为了取整。

2、5比中间数10小。将high指针移动到mid左边（同理，如果大于就将low移动到mid右边）。然后计算出新的mid位置

此时key和中间元素相等，匹配成功，查找结束。

如果我们找的是2，2比mid还小，我们需要将high继续移动到mid左边

此时，再计算mid 为 0+0/2 还是 0 将 mid移动到下标为0的位置。然后进行判断，然后找到2。

算法实现：

参考于：

https://www.bilibili.com/video/BV1LJ411X76n

https://blog.csdn.net/m0_66769266/article/details/124212178

https://network.51cto.com/article/688182.html

https://www.csdn.net/tags/MtTaMg4sOTgxNDk5LWJsb2cO0O0O.html

https://blog.51cto.com/u_15246373/3062445

https://blog.csdn.net/weixin_41489378/article/details/119701190