店小二：掌柜的，您進(jìn)貨回來了呀，喲！今天您買這魚挺大呀！袁廚：那是，這是我今天從咱們江邊買的，之前一直去菜市場(chǎng)買，那里的老貴了，你猜猜我今天買的多少錢一條。店小二：之前的魚，30 個(gè)銅板一條，今天的我猜 26 個(gè)銅板。袁廚：貴了。店小二：還貴呀！那我猜 20 個(gè)銅板！袁廚：還是貴了。店小二：15 個(gè)銅板。袁廚：便宜了店小二：18 個(gè)銅板袁廚：恭喜你猜對(duì)了
上面的例子就用到了我們的二分查找思想，如果你玩過類似的游戲，那二分查找理解起來肯定很輕松啦。
二分查找
二分查找也稱折半查找（Binary Search），是一種在有序數(shù)組中查找某一特定元素的搜索算法。我們可以從定義可知，運(yùn)用二分搜索的前提是數(shù)組必須是有序的，這里需要注意的是，我們的輸入不一定是數(shù)組，也可以是數(shù)組中某一區(qū)間的起始位置和終止位置。通過上面二分查找的定義，我們知道了二分查找算法的作用及要求，那么該算法的具體執(zhí)行過程是怎樣的呢？下面我們通過一個(gè)例子來幫助我們理解。我們需要在 nums 數(shù)組中，查詢?cè)?8 的索引。
-
找出 mid，該索引為 mid =（left + right）/ 2，但是這樣寫有可能溢出，所以我們需要改進(jìn)一下寫成 mid = left +（right - left）/ 2 或者 left + ((right - left ) >> 1) 兩者作用是一樣的，都是為了找到兩指針的中間索引，使用位運(yùn)算的速度更快。那么此時(shí)的 mid = 0 + (8-0) / 2 = 4圖片
二分查找的執(zhí)行過程如下
****二分查找的執(zhí)行過程如下****
從已經(jīng)排好序的數(shù)組或區(qū)間中，取出中間位置的元素，將其與我們的目標(biāo)值進(jìn)行比較，判斷是否相等，如果相等則返回。
如果 nums[mid] 和 target 不相等，則對(duì) nums[mid] 和 target 值進(jìn)行比較大小，通過比較結(jié)果決定是從 mid的左半部分還是右半部分繼續(xù)搜索。
如果 target > nums[mid] 則右半?yún)^(qū)間繼續(xù)進(jìn)行搜索，即 left = mid + 1; 若target < nums[mid] 則在左半?yún)^(qū)間繼續(xù)進(jìn)行搜索，即 right = mid -1；動(dòng)圖解析
二分查找的思路及代碼已經(jīng)理解了，那么我們來看一下實(shí)現(xiàn)時(shí)容易出錯(cuò)的地方。 易錯(cuò)點(diǎn)：
計(jì)算 mid 時(shí) ，不能使用 （left + right ）/ 2，否則有可能會(huì)導(dǎo)致溢出
while (left < = right)，注意括號(hào)內(nèi)為 left <= right ，而不是 left < right ，我們繼續(xù)回顧剛才的例子，如果我們?cè)O(shè)置條件為 left < right 則當(dāng)我們執(zhí)行到最后一步時(shí)，則我們的 left 和 right 重疊時(shí)，則會(huì)跳出循環(huán)，返回 -1，區(qū)間內(nèi)不存在該元素，但是不是這樣的，我們的 left 和 right 此時(shí)指向的就是我們的目標(biāo)元素 ，但是此時(shí) left = right 跳出循環(huán)
left = mid + 1,right = mid - 1 而不是 left = mid 和 right = mid。我們思考一下這種情況,見下圖，當(dāng)我們的target 元素為 16 時(shí)，然后我們此時(shí) left = 7 ，right = 8，mid = left + (right - left) = 7 + (8-7) = 7，那如果設(shè)置 left = mid 的話，則會(huì)進(jìn)入死循環(huán)，mid 值一直為7 。
下面我們來看一下二分查找的遞歸寫法
例題及解析
例題：
題目來源：leetcode35 搜索插入位置 給定一個(gè)排序數(shù)組和一個(gè)目標(biāo)值，在數(shù)組中找到目標(biāo)值，并返回其索引。如果目標(biāo)值不存在于數(shù)組中，返回它將會(huì)被按順序插入的位置。你可以假設(shè)數(shù)組中無重復(fù)元素。示例 1:
輸入: [1,3,5,6], 5 輸出: 2
示例 2:
輸入: [1,3,5,6], 2 輸出: 1
示例 3:
輸入: [1,3,5,6], 7 輸出: 4
示例 4:
輸入: [1,3,5,6], 0 輸出: 0
題目解析
這個(gè)題目完全就和咱們的二分查找一樣，只不過有了一點(diǎn)改寫，那就是將咱們的返回值改成了 left，具體實(shí)現(xiàn)過程見下圖二分查找變種一
上面我們說了如何使用二分查找在數(shù)組或區(qū)間里查出特定值的索引位置。但是我們剛才數(shù)組里面都沒有重復(fù)值，查到返回即可，那么我們思考一下下面這種情況：此時(shí)我們數(shù)組里含有多個(gè) 5 ，我們查詢是否含有 5 可以很容易查到，但是我們想獲取第一個(gè) 5 和 最后一個(gè) 5 的位置應(yīng)該怎么實(shí)現(xiàn)呢？哦！我們可以使用遍歷，當(dāng)查詢到第一個(gè) 5 時(shí)，我們?cè)O(shè)立一個(gè)指針進(jìn)行定位，然后到達(dá)最后一個(gè) 5 時(shí)返回，這樣我們就能求的第一個(gè)和最后一個(gè)五了？因?yàn)槲覀冞@個(gè)文章的主題就是二分查找，我們可不可以用二分查找來實(shí)現(xiàn)呢？當(dāng)然是可以的。
題目描述
題目來源：leetcode 34 在排序數(shù)組中查找元素的第一個(gè)和最后一個(gè)位置給定一個(gè)按照升序排列的整數(shù)數(shù)組 nums，和一個(gè)目標(biāo)值 target。找出給定目標(biāo)值在數(shù)組中的開始位置和結(jié)束位置。如果數(shù)組中不存在目標(biāo)值 target，返回 [-1, -1]。示例 1：
輸入：nums = [5,7,7,8,8,10], target = 8 輸出：[3,4]
示例 2：
輸入：nums = [5,7,7,8,8,10], target = 6 輸出：[-1,-1]
示例 3：
輸入：nums = [], target = 0 輸出：[-1,-1]
題目解析
這個(gè)題目很容易理解，我們?cè)谏厦嬲f了如何使用遍歷解決該題，但是這個(gè)題目的目的就是讓我們使用二分查找，我們來逐個(gè)分析，先找出目標(biāo)元素的下邊界，那么我們?nèi)绾握业侥繕?biāo)元素的下邊界呢？我們來重點(diǎn)分析一下剛才二分查找中的這段代碼其實(shí)原理很簡(jiǎn)單，就是我們將小于和等于合并在一起處理，當(dāng) target <= nums[mid] 時(shí)，我們都移動(dòng)右指針，也就是 right = mid -1，還有一個(gè)需要注意的就是，我們計(jì)算下邊界時(shí)最后的返回值為 left ，當(dāng)上圖結(jié)束循環(huán)時(shí)，left = 3，right = 2，返回 left 剛好時(shí)我們的下邊界。我們來看一下求下邊界的具體執(zhí)行過程。動(dòng)圖解析
二分查找變種二
我們?cè)谏厦娴淖兎N中，描述了如何找出目標(biāo)元素在數(shù)組中的上下邊界，然后我們下面來看一個(gè)新的變種，如何從數(shù)組或區(qū)間中找出第一個(gè)大于或最后一個(gè)小于目標(biāo)元素的數(shù)的索引，例 nums = {1,3,5,5,6,6,8,9,11} 我們希望找出第一個(gè)大于 5的元素的索引，那我們需要返回 4 ，因?yàn)?5 的后面為 6，第一個(gè) 6 的索引為 4，如果希望找出最后一個(gè)小于 6 的元素，那我們則會(huì)返回 3 ，因?yàn)?6 的前面為 5 最后一個(gè) 5 的索引為 3。題目我們已經(jīng)了解，下面我們先來看一下如何在數(shù)組或區(qū)間中找出第一個(gè)大于目標(biāo)元素的數(shù)吧。找出第一個(gè)大于目標(biāo)元素的數(shù)，大概有以下幾種情況數(shù)組包含目標(biāo)元素，找出在他后面的第一個(gè)元素；
目標(biāo)元素不在數(shù)組中，且數(shù)組中的所有元素都大于它，那么我們此時(shí)返回?cái)?shù)組的第一個(gè)元素即可；
目標(biāo)元素不在數(shù)組中，數(shù)組內(nèi)的部分元素大于它，此時(shí)我們需要返回第一個(gè)大于他的元素；
目標(biāo)元素不在數(shù)組中，且數(shù)組中的所有元素都小于它，那么我們此時(shí)沒有查詢到，返回 -1 即可。
既然我們已經(jīng)分析完所有情況，那么這個(gè)題目對(duì)咱們就沒有難度了，下面我們描述一下案例的執(zhí)行過程
上面的例子中，我們需要找出第一個(gè)大于 7 的數(shù)，那么我們的程序是如何執(zhí)行的呢？上面的例子我們已經(jīng)弄懂了，那么我們看一下，當(dāng) target = 0時(shí)，程序應(yīng)該怎么執(zhí)行呢？nums = {1,3,5,5,6,6,8,9,11} target = 7
通過上面的例子我們應(yīng)該可以完全理解了那個(gè)變種。下面我們繼續(xù)來看以下這種情況，那就是如何找到最后一個(gè)小于目標(biāo)數(shù)的元素。還是上面那個(gè)例子
查找最后一個(gè)小于目標(biāo)數(shù)的元素，比如我們的目標(biāo)數(shù)為 7 ，此時(shí)他前面的數(shù)為 6，最后一個(gè) 6 的索引為 5，此時(shí)我們返回 5 即可，如果目標(biāo)數(shù)元素為 12，那么我們最后一個(gè)元素為 11，仍小于目標(biāo)數(shù)，那么我們此時(shí)返回 8，即可。這個(gè)變種其實(shí)算是上面變種的相反情況，上面的會(huì)了，這個(gè)也完全可以搞定了，下面我們看一下代碼吧。nums = {1,3,5,5,6,6,8,9,11} target = 7
