二分查找法是非常經(jīng)典的一種查找法，每個(gè)程序員都應(yīng)該理解并熟練掌握。

1. 算法使用前提：數(shù)組是有序數(shù)組,且無重復(fù)元素

2. 基本原理：

首先將要查找的元素(key)與數(shù)組的中間元素比較

1、如果key小于中間元素，只需要在數(shù)組的前一半元素中繼續(xù)查找

2、如果key和中間元素相等，匹配成功，查找結(jié)束

3、如果key大于中間元素，只需要在數(shù)組的后一半元素中繼續(xù)查找

3. 復(fù)雜度：時(shí)間復(fù)雜度O(logn)；循環(huán)實(shí)現(xiàn)空間復(fù)雜度為O(1)

運(yùn)行速度O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)<O(2?)<O(n!)

4. 過程圖示：

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

1、首先定義頭尾指針，算出中間指針。本文中間數(shù)算法是向下取整mid=(start+end)/2|0。位運(yùn)算|0作用是向下取整。

所有的按位操作符的操作數(shù)都會(huì)被轉(zhuǎn)成補(bǔ)碼形式的有符號(hào)32位整數(shù)。也就是如果有小數(shù)則忽略。而0 轉(zhuǎn)為二進(jìn)制則為 000000......(32位) 。然后一一比較，還是原來上面的值。所以只是為了取整。

2、5比中間數(shù)10小。將high指針移動(dòng)到mid左邊（同理，如果大于就將low移動(dòng)到mid右邊）。然后計(jì)算出新的mid位置

此時(shí)key和中間元素相等，匹配成功，查找結(jié)束。

如果我們找的是2，2比mid還小，我們需要將high繼續(xù)移動(dòng)到mid左邊

此時(shí)，再計(jì)算mid 為 0+0/2 還是 0 將 mid移動(dòng)到下標(biāo)為0的位置。然后進(jìn)行判斷，然后找到2。

算法實(shí)現(xiàn)：

參考于：

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