作者 | 袁廚 責(zé)編 | 張文

頭圖 | CSDN 下載自視覺中國

來源 | 袁廚的算法小屋(ID：tan45du_me)

今天給大家?guī)淼氖嵌植檎壹捌渥兎N的總結(jié)。

袁記菜館內(nèi)。

店小二：掌柜的，您進(jìn)貨回來了呀，喲！今天您買這魚挺大呀！

袁廚：那是，這是我今天從咱們江邊買的，之前一直去菜市場買，那里的老貴了，你猜猜我今天買的多少錢一條。

店小二：之前的魚，30 個銅板一條，今天的我猜 26 個銅板。

袁廚：貴了。

店小二：還貴呀！那我猜 20 個銅板！

袁廚：還是貴了。

店小二：15 個銅板。

袁廚：便宜了

店小二：18 個銅板

袁廚：恭喜你猜對了

上面的例子就用到了我們的二分查找思想，如果你玩過類似的游戲，那二分查找理解起來肯定很輕松啦。

二分查找

二分查找也稱折半查找(Binary Search)，是一種在有序數(shù)組中查找某一特定元素的搜索算法。我們可以從定義可知，運(yùn)用二分搜索的前提是數(shù)組必須是有序的，這里需要注意的是，我們的輸入不一定是數(shù)組，也可以是數(shù)組中某一區(qū)間的起始位置和終止位置。

通過上面二分查找的定義，我們知道了二分查找算法的作用及要求，那么該算法的具體執(zhí)行過程是怎樣的呢？

下面我們通過一個例子來幫助我們理解。我們需要在 nums 數(shù)組中，查詢元素 8 的索引。

1. 我們需要定義兩個指針分別指向數(shù)組的頭部及尾部，這是我們在整個數(shù)組中查詢的情況，當(dāng)我們在數(shù)組某一區(qū)間進(jìn)行查詢時，可以輸入數(shù)組，起始位置，終止位置進(jìn)行查詢。

2. 找出 mid，該索引為 mid =(left + right)/ 2，但是這樣寫有可能溢出，所以我們需要改進(jìn)一下寫成 mid = left +(right - left)/ 2 或者 left + ((right - left ) >> 1) 兩者作用是一樣的，都是為了找到兩指針的中間索引，使用位運(yùn)算的速度更快。那么此時的 mid = 0 + (8-0) / 2 = 4

3. 此時我們的 mid = 4，nums[mid] = 6 < target，那么我們需要

移動我們的 left 指針，讓left = mid + 1，下次則可以在新的 left 和 right 區(qū)間內(nèi)搜索目標(biāo)值

，下圖為移動前和移動后

4. 我們需要在 left 和 right 之間計算 mid 值，mid = 5 + (8 - 5)/ 2 = 6 然后將 nums[mid] 與 target 繼續(xù)比較，進(jìn)而決定下次移動left 指針還是 right 指針，見下圖

5. 我們發(fā)現(xiàn)

nums[mid] > target，則需要移動我們的 right 指針

， 則 right = mid - 1；則移動過后我們的 left 和 right 會重合，這里是我們的一個重點(diǎn)大家需要注意一下，后面會對此做詳細(xì)敘述。

6. 我們需要在 left 和 right 之間繼續(xù)計算 mid 值，則 mid = 5 +(5 - 5)/ 2 = 5 ，見下圖，此時我們將 nums[mid] 和 target 比較，則發(fā)現(xiàn)兩值相等，返回 mid 即可 ，如果不相等則跳出循環(huán)，返回 -1。

二分查找的執(zhí)行過程如下

二分查找的執(zhí)行過程如下

• 從已經(jīng)排好序的數(shù)組或區(qū)間中，取出中間位置的元素，將其與我們的目標(biāo)值進(jìn)行比較，判斷是否相等，如果相等則返回。

• 如果 nums[mid] 和 target 不相等，則對 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；

動圖解析

下面我們來看一下二分查找的代碼，可以認(rèn)真思考一下 if 語句的條件，每個都沒有簡寫。

二分查找的思路及代碼已經(jīng)理解了，那么我們來看一下實現(xiàn)時容易出錯的地方。

易錯點(diǎn)：

計算 mid 時 ，不能使用 (left + right )/ 2，否則有可能會導(dǎo)致溢出

while (left < = right)，注意括號內(nèi)為 left <= right ，而不是 left < right ，我們繼續(xù)回顧剛才的例子，如果我們設(shè)置條件為 left < right 則當(dāng)我們執(zhí)行到最后一步時，則我們的 left 和 right 重疊時，則會跳出循環(huán)，返回 -1，區(qū)間內(nèi)不存在該元素，但是不是這樣的，我們的 left 和 right 此時指向的就是我們的目標(biāo)元素 ，但是此時 left = right 跳出循環(huán)

left = mid + 1,right = mid - 1 而不是 left = mid 和 right = mid。我們思考一下這種情況,見下圖，當(dāng)我們的target 元素為 16 時，然后我們此時 left = 7 ，right = 8，mid = left + (right - left) = 7 + (8-7) = 7，那如果設(shè)置 left = mid 的話，則會進(jìn)入死循環(huán)，mid 值一直為7 。

下面我們來看一下二分查找的遞歸寫法

例題及解析

例題：

題目來源：leetcode35 搜索插入位置

給定一個排序數(shù)組和一個目標(biāo)值，在數(shù)組中找到目標(biāo)值，并返回其索引。如果目標(biāo)值不存在于數(shù)組中，返回它將會被按順序插入的位置。

你可以假設(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

題目解析

這個題目完全就和咱們的二分查找一樣，只不過有了一點(diǎn)改寫，那就是將咱們的返回值改成了 left，具體實現(xiàn)過程見下圖

二分查找變種一

上面我們說了如何使用二分查找在數(shù)組或區(qū)間里查出特定值的索引位置。但是我們剛才數(shù)組里面都沒有重復(fù)值，查到返回即可，那么我們思考一下下面這種情況：

此時我們數(shù)組里含有多個 5 ，我們查詢是否含有 5 可以很容易查到，但是我們想獲取第一個 5 和 最后一個 5 的位置應(yīng)該怎么實現(xiàn)呢？

哦！我們可以使用遍歷，當(dāng)查詢到第一個 5 時，我們設(shè)立一個指針進(jìn)行定位，然后到達(dá)最后一個 5 時返回，這樣我們就能求的第一個和最后一個五了？因為我們這個文章的主題就是二分查找，我們可不可以用二分查找來實現(xiàn)呢？當(dāng)然是可以的。

題目描述

題目來源：leetcode 34 在排序數(shù)組中查找元素的第一個和最后一個位置

給定一個按照升序排列的整數(shù)數(shù)組 nums，和一個目標(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]

題目解析

這個題目很容易理解，我們在上面說了如何使用遍歷解決該題，但是這個題目的目的就是讓我們使用二分查找，我們來逐個分析，先找出目標(biāo)元素的下邊界，那么我們?nèi)绾握业侥繕?biāo)元素的下邊界呢？

我們來重點(diǎn)分析一下剛才二分查找中的這段代碼

我們只需在這段代碼中修改即可，我們再來剖析一下這塊代碼，

nums[mid] == target 時則返回，nums[mid] < target 時則移動左指針，在右區(qū)間進(jìn)行查找， nums[mid] > target 時則移動右指針，在左區(qū)間內(nèi)進(jìn)行查找。

那么我們思考一下，如果此時我們的 nums[mid] = target ，但是我們不能確定 mid 是否為該目標(biāo)數(shù)的左邊界，所以此時我們不可以返回下標(biāo)。例如下面這種情況。

此時 mid = 4 ，nums[mid] = 5，但是此時的 mid 指向的并不是第一個 5，所以我們需要繼續(xù)查找 ，因為我們要找的是數(shù)的下邊界，所以我們需要在 mid 的值的左區(qū)間繼續(xù)尋找 5 ，那我們應(yīng)該怎么做呢？

我們只需在target <= nums[mid] 時，讓 right = mid - 1即可，這樣我們就可以繼續(xù)在 mid 的左區(qū)間繼續(xù)找 5 。是不是聽著有點(diǎn)繞，我們通過下面這組圖進(jìn)行描述。

其實原理很簡單，就是我們將小于和等于合并在一起處理，當(dāng) target <= nums[mid] 時，我們都移動右指針，也就是 right = mid -1，還有一個需要注意的就是，我們計算下邊界時最后的返回值為 left ，當(dāng)上圖結(jié)束循環(huán)時，left = 3，right = 2，返回 left 剛好時我們的下邊界。我們來看一下求下邊界的具體執(zhí)行過程。

動圖解析

計算下邊界代碼

計算上邊界時算是和計算上邊界時條件相反，

計算下邊界時，當(dāng) target <= nums[mid] 時，right = mid -1；target > nums[mid] 時，left = mid + 1；

計算上邊界時，當(dāng) target < nums[mid] 時，right = mid -1; target >= nums[mid] 時 left = mid + 1;剛好和計算下邊界時條件相反，返回right。

計算上邊界代碼

題目完整代碼

二分查找變種二

我們在上面的變種中，描述了如何找出目標(biāo)元素在數(shù)組中的上下邊界，然后我們下面來看一個新的變種，如何從數(shù)組或區(qū)間中找出第一個大于或最后一個小于目標(biāo)元素的數(shù)的索引，例 nums = {1,3,5,5,6,6,8,9,11} 我們希望找出第一個大于 5的元素的索引，那我們需要返回 4 ，因為 5 的后面為 6，第一個 6 的索引為 4，如果希望找出最后一個小于 6 的元素，那我們則會返回 3 ，因為 6 的前面為 5 最后一個 5 的索引為 3。

題目我們已經(jīng)了解，下面我們先來看一下如何在數(shù)組或區(qū)間中找出第一個大于目標(biāo)元素的數(shù)吧。

找出第一個大于目標(biāo)元素的數(shù)，大概有以下幾種情況

數(shù)組包含目標(biāo)元素，找出在他后面的第一個元素；

目標(biāo)元素不在數(shù)組中，且數(shù)組中的所有元素都大于它，那么我們此時返回數(shù)組的第一個元素即可；

目標(biāo)元素不在數(shù)組中，數(shù)組內(nèi)的部分元素大于它，此時我們需要返回第一個大于他的元素；

目標(biāo)元素不在數(shù)組中，且數(shù)組中的所有元素都小于它，那么我們此時沒有查詢到，返回 -1 即可。

既然我們已經(jīng)分析完所有情況，那么這個題目對咱們就沒有難度了，下面我們描述一下案例的執(zhí)行過程

nums = {1,3,5,5,6,6,8,9,11} target = 7

上面的例子中，我們需要找出第一個大于 7 的數(shù)，那么我們的程序是如何執(zhí)行的呢？

上面的例子我們已經(jīng)弄懂了，那么我們看一下，當(dāng) target = 0時，程序應(yīng)該怎么執(zhí)行呢？

OK！我們到這一步就能把這個變種給整的明明白白的了，下面我們看一哈程序代碼吧，也是非常簡單的。

通過上面的例子我們應(yīng)該可以完全理解了那個變種。

下面我們繼續(xù)來看以下這種情況，那就是如何找到最后一個小于目標(biāo)數(shù)的元素。還是上面那個例子

nums = {1,3,5,5,6,6,8,9,11} target = 7

查找最后一個小于目標(biāo)數(shù)的元素，比如我們的目標(biāo)數(shù)為 7 ，此時他前面的數(shù)為 6，最后一個 6 的索引為 5，此時我們返回 5 即可，如果目標(biāo)數(shù)元素為 12，那么我們最后一個元素為 11，仍小于目標(biāo)數(shù)，那么我們此時返回 8，即可。這個變種其實算是上面變種的相反情況，上面的會了，這個也完全可以搞定了，下面我們看一下代碼吧。

課后作業(yè)：

思考一下如果數(shù)組不完全有序我們可以用二分查找嗎？

點(diǎn)分享

總結(jié)

以上是生活随笔為你收集整理的access 查找工龄大于30_面试前必知必会的二分查找及其变种的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。