店小二：掌柜的，您進(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
