二分查找及其變種的總結(jié)

今天給大家?guī)淼氖嵌植檎壹捌渥兎N的總結(jié)，大家一定要看到最后呀，非常非常用心的一篇文章，廢話不多說，讓導(dǎo)演幫我們把鏡頭切到袁記菜館吧！

袁記菜館內(nèi)。。。。

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

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

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

袁廚：貴了。

店小二：還貴呀！那我猜20個(gè)銅板！

袁廚：還是貴了。

店小二：15個(gè)銅板。

袁廚：便宜了

店小二：18個(gè)銅板

袁廚：恭喜你猜對了

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

完全有序

二分查找

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

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

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

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

（2）找出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

（3）此時(shí)我們的 mid = 4，nums[mid] = 6 < target,那么我們需要移動(dòng)我們的 left 指針，讓left = mid + 1，下次則可以在新的 left 和 right 區(qū)間內(nèi)搜索目標(biāo)值，下圖為移動(dòng)前和移動(dòng)后

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

（5）我們發(fā)現(xiàn) nums[mid] > target，則需要移動(dòng)我們的 right 指針， 則 right = mid - 1；則移動(dòng)過后我們的 left 和 right 會(huì)重合，這里是我們的一個(gè)重點(diǎn)大家需要注意一下，后面會(huì)對此做詳細(xì)敘述。

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

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

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

2.如果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；

動(dòng)圖解析

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

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

1.計(jì)算 mid 時(shí)，不能使用 （left + right ）/ 2,否則有可能會(huì)導(dǎo)致溢出

2. while (left < = right) ?注意括號內(nèi)為 left <= right?,而不是 left < right ，我們繼續(xù)回顧剛才的例子，如果我們設(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)

3.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)過程見下圖

題目代碼

查找元素第一個(gè)位置和最后一個(gè)位置

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

此時(shí)我們數(shù)組里含有多個(gè) 5 ，我們查詢是否含有 5 可以很容易查到，但是我們想獲取第一個(gè) 5 和 最后一個(gè) 5 的位置應(yīng)該怎么實(shí)現(xiàn)呢？哦！我們可以使用遍歷，當(dāng)查詢到第一個(gè) 5 時(shí)，我們設(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è)題目很容易理解，我們在上面說了如何使用遍歷解決該題，但是這個(gè)題目的目的就是讓我們使用二分查找，我們來逐個(gè)分析，先找出目標(biāo)元素的下邊界，那么我們?nèi)绾握业侥繕?biāo)元素的下邊界呢？

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

我們只需在這段代碼中修改即可，我們再來剖析一下這塊代碼，nums[mid] == target 時(shí)則返回，nums[mid] < target 時(shí)則移動(dòng)左指針，在右區(qū)間進(jìn)行查找， nums[mid] ?> target時(shí)則移動(dòng)右指針，在左區(qū)間內(nèi)進(jìn)行查找。

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

此時(shí) mid = 4 ，nums[mid] = 5,但是此時(shí)的 mid 指向的并不是第一個(gè) 5，所以我們需要繼續(xù)查找 ，因?yàn)槲覀円业氖菙?shù)的下邊界，所以我們需要在 mid 的值的左區(qū)間繼續(xù)尋找 5 ，那我們應(yīng)該怎么做呢？

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

其實(shí)原理很簡單，就是我們將小于和等于合并在一起處理，當(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)圖解析

計(jì)算下邊界代碼

計(jì)算上邊界時(shí)算是和計(jì)算上邊界時(shí)條件相反，

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

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

計(jì)算上邊界代碼

題目完整代碼

找出第一個(gè)大于目標(biāo)元素的索引

我們在上面的變種中，描述了如何找出目標(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ù)，大概有以下幾種情況

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

2.目標(biāo)元素不在數(shù)組中，且數(shù)組中的所有元素都大于它，那么我們此時(shí)返回?cái)?shù)組的第一個(gè)元素即可

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

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

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

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

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

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

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

找出第一個(gè)小于目標(biāo)元素的索引

通過上面的例子我們應(yīng)該可以完全理解了那個(gè)變種，下面我們繼續(xù)來看以下這種情況，那就是如何找到最后一個(gè)小于目標(biāo)數(shù)的元素。還是上面那個(gè)例子

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

查找最后一個(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è)也完全可以搞定了，下面我們看一下代碼吧。

不完全有序

查找目標(biāo)元素（不含重復(fù)元素）

上面我們說二分查找需要在完全有序的數(shù)組里使用，那么不完全有序時(shí)可以使用二分查找嗎？我們一起往下看吧。

例：

我們需要在上面的數(shù)組中查找我們的target，但是這個(gè)數(shù)組不是完全有序的應(yīng)該怎么辦呢？ 上面的新數(shù)組雖然不是完全有序，但是我們也可以找到規(guī)律，可以看成是由一個(gè)完全有序的數(shù)組旋轉(zhuǎn)得到的?；蛘呖梢岳斫獬蓛蓚€(gè)有序數(shù)組，且第二個(gè)數(shù)組的最大值小于第一的最小值，我們將其拼接，拼接成了一個(gè)不完全有序的數(shù)組，在這個(gè)數(shù)組中我們需要找到 target ，找到后返回其索引，如果沒有找到則返回 -1；

下面我們看一下用二分查找解決該題的具體思路。 首先我們先設(shè)想一下mid值會(huì)落到哪里？ 是不是只有兩種情況，和 left 在一個(gè)數(shù)組，同時(shí)落在數(shù)組1或同時(shí)在數(shù)組2，或者不在一個(gè)數(shù)組， left 在數(shù)組1，mid 在數(shù)組2。想到這里咱們這個(gè)題目已經(jīng)完成一半了，見下圖。

那么我們先來思考一下，我們怎么才能知道 left 和 mid 有沒有在一個(gè)數(shù)組里呢？

我們可以通過nums[mid] 和 nums[left] 比較進(jìn)行判斷，因?yàn)槲覀兊膍id 一定是會(huì)落在 left 和 right 之間，那如果nums[mid] >= nums[left] 時(shí)，說明他倆落在一個(gè)數(shù)組里了，如果nums[mid] < nums[left]? 時(shí)，說明他倆落在了不同的數(shù)組，此時(shí)?left 在數(shù)組1 ，mid在數(shù)組2。

為什么我們可以通過這個(gè)進(jìn)行判斷呢？我們想一下，如果left 和 mid 在 同一個(gè)數(shù)組里，且mid 一定在 left 的后面，在一個(gè)數(shù)組里，數(shù)組又是遞增的，那么nums[mid]> nums[left], 如果 nums[mid]< nums[left]?，且 mid 在 left 的后面，則說明 left 在數(shù)組1，mid 在數(shù)組2。

那么當(dāng)left 和 mid 落在不同數(shù)組時(shí)，為什么不能是 left 在 數(shù)組2 ，mid 在 數(shù)組1 呢？

因?yàn)樵蹅兊膍id 是通過 left 和 right 的下標(biāo)求得，所以mid 應(yīng)該在 left 和 right 中間

如果我們的mid 和 left 在同一個(gè)數(shù)組內(nèi)時(shí)？咱們的target會(huì)有幾種情況呢？

見下圖

無非也是兩種情況，用我們上面的例子來說，

1.落在 mid 的左邊，target = 5，當(dāng)前例子中 情況是落在[4,7）區(qū)間內(nèi)，即 4 <= target < ?7 ，也就是??target ?>= nums[left] && target < nums[mid]，此時(shí)我們讓??right = mid -1，讓 left 和 right 都落到數(shù)組 1 中，下次查找我們就是在數(shù)組1中進(jìn)行了，完全有序，

2.落在 mid 的右邊，target = 1 ，target = 8 ，此時(shí)例子中 target 不落在 [4,7）區(qū)間內(nèi)，那就target = 8或0 <= ?target <= 2（此時(shí)我們的 target 均小于 nums[left]） 兩種情況，也就是?target > nums[mid] || target < nums[left]??此時(shí)我們讓??left = mid + 1?即可，也是為了慢慢將left 和 right 指針趕到一個(gè)有序區(qū)間內(nèi)。

那我們在來思考一下當(dāng) mid 值落在數(shù)組2中時(shí)，target 會(huì)有幾種情況呢？其實(shí)和上面的例子思路一致，情況相反而已。

1. target <= nums[right] && target > nums[mid] 這里和上面的對應(yīng)，此時(shí)的情況就是整個(gè)落在右半部分，我們下次就可以在數(shù)組2內(nèi)進(jìn)行查找。 2. target > nums[right] || target < nums[mid] 這里就是和上面的第二種情況對應(yīng)，落在 mid 的左半部分，我們盡量將兩個(gè)指針趕到一個(gè)完全有序的區(qū)間內(nèi)

通過上面的例子大家應(yīng)該對該變種有所了解了，下面我們一起來做一下 leetcode 33 題吧。

leetcode33搜索旋轉(zhuǎn)排序數(shù)組

題目描述

給你一個(gè)整數(shù)數(shù)組 nums ，和一個(gè)整數(shù) target 。

該整數(shù)數(shù)組原本是按升序排列，但輸入時(shí)在預(yù)先未知的某個(gè)點(diǎn)上進(jìn)行了旋轉(zhuǎn)。（例如，數(shù)組 [0,1,2,4,5,6,7] 可能變?yōu)?[4,5,6,7,0,1,2] ）。

請你在數(shù)組中搜索 target ，如果數(shù)組中存在這個(gè)目標(biāo)值，則返回它的索引，否則返回 -1 。

示例 1：

輸入：nums = [4,5,6,7,0,1,2], target = 0 輸出：4

示例 2：

輸入：nums = [4,5,6,7,0,1,2], target = 3 輸出：-1

示例 3：

輸入：nums = [1], target = 0 輸出：-1

題目解析

這個(gè)題目的解答方法，咱們在上面已經(jīng)有所描述，下面我們來看一下下面這個(gè)例子的代碼執(zhí)行過程吧.大家可以結(jié)合代碼和動(dòng)圖進(jìn)行理解，代碼中所有語句都沒有進(jìn)行簡寫，可以仔細(xì)閱讀判斷條件，很容易理解。

輸入 nums = [4,5,6,7,8,0,1,2] target = 8

動(dòng)圖解析

下面我們看題目代碼吧，如果還沒有完全理解的同學(xué)，可以仔細(xì)閱讀 if ，else if 里面的語句，（沒有簡寫）還有文中注釋，一定可以整透的。

題目代碼

查找目標(biāo)元素（含重復(fù)元素）我們通過剛才的例子了解了，如果在不完全有序的數(shù)組中查找目標(biāo)元素，但是我們的不完全有序數(shù)組中是不包含重復(fù)元素的，那如果我們的數(shù)組中包含重復(fù)元素我們應(yīng)該怎么做呢？見下圖

如上圖，如果我們繼續(xù)使用剛才的代碼，則會(huì)報(bào)錯(cuò)這是為什么呢?我們來分析一下。

所以我們需要對其進(jìn)行改進(jìn)，我們只需將重復(fù)元素去掉即可，當(dāng)我們的 nums[left] == nums[mid]時(shí)，讓 left ++ 即可，比如 1，3，1，1，1此時(shí) nums[mid] == nums[left] 則 left ++,那我們此時(shí)會(huì)不會(huì)錯(cuò)過目標(biāo)值呢？其實(shí)并不會(huì)，只是去掉了某些重復(fù)元素，如果此時(shí)我們的目標(biāo)元素是3，則我們left++，之后情況就變?yōu)榱松项}中的情況。 leetcode81. 搜索旋轉(zhuǎn)排序數(shù)組 II 題目描述

假設(shè)按照升序排序的數(shù)組在預(yù)先未知的某個(gè)點(diǎn)上進(jìn)行了旋轉(zhuǎn)。

( 例如，數(shù)組 [0,0,1,2,2,5,6] 可能變?yōu)?[2,5,6,0,0,1,2] )。

編寫一個(gè)函數(shù)來判斷給定的目標(biāo)值是否存在于數(shù)組中。若存在返回 true，否則返回 false。

示例 1：

輸入：nums = [2,5,6,0,0,1,2], target = 0 輸出：true

示例 2：

輸入：nums = [2,5,6,0,0,1,2], target = 3 輸出：false

題目解析這個(gè)題目就比剛才的不含重復(fù)元素的題目多了一個(gè)去除某些重復(fù)元素的情況，當(dāng) nums[mid] == nums[left]時(shí)，讓left++，并退出本次循環(huán)，其余部分完全相同，大家可以結(jié)合代碼和圖片進(jìn)行理解。題目代碼

尋找最小值 這種情況也很容易處理，和咱們的leetcode33搜索旋轉(zhuǎn)排序數(shù)組，題目類似，只不過一個(gè)需要搜索目標(biāo)元素，一個(gè)搜索最小值，我們搜索目標(biāo)元素很容易處理，但是我們搜索最小值應(yīng)該怎么整呢？見下圖

我們需要在一個(gè)旋轉(zhuǎn)數(shù)組中，查找其中的最小值，如果我們數(shù)組是完全有序的很容易，我們只需要返回第一個(gè)元素即可，但是此時(shí)我們是旋轉(zhuǎn)過的數(shù)組。 我們需要考慮以下情況

我們見上圖，我們需要考慮的情況是

數(shù)組完全有序nums[left] < nums[right]，此時(shí)返回?nums[left]?即可

left 和 mid 在一個(gè)都在前半部分，單調(diào)遞增區(qū)間內(nèi)，所以需要移動(dòng) left，繼續(xù)查找，left= mid + 1；

left 在前半部分，mid在后半部分，則最小值必在 left 和 mid 之間（見下圖）。則需要移動(dòng)right ，right = mid，我們見上圖，如果我們 right = mid - 1，則會(huì)漏掉我們的最小值，因?yàn)榇藭r(shí) mid 指向的可能就是我們的最小值。所以應(yīng)該是 right = mid 。

leetcode 153尋找旋轉(zhuǎn)數(shù)組中的最小值

題目描述

假設(shè)按照升序排序的數(shù)組在預(yù)先未知的某個(gè)點(diǎn)上進(jìn)行了旋轉(zhuǎn)。例如，數(shù)組 [0,1,2,4,5,6,7] 可能變?yōu)?[4,5,6,7,0,1,2] 。

請找出其中最小的元素。

示例 1：

輸入：nums = [3,4,5,1,2]輸出：1

示例 2：

輸入：nums = [4,5,6,7,0,1,2]輸出：0

示例 3：

輸入：nums = [1]輸出:1

題目解析

我們在上面的描述中已經(jīng)和大家分析過幾種情況，下面我們一起來看一下，[5,6,7,0,1,2,3]的執(zhí)行過程，相信通過這個(gè)例子，大家就能把這個(gè)題目整透了。

題目代碼

二維數(shù)組

查找目標(biāo)元素

下面我們來看一下另外一種變體，如何在二維矩陣?yán)锸褂枚植檎夷兀?/p>

其實(shí)這個(gè)很簡單，只要學(xué)會(huì)了二分查找，這個(gè)完全可以解決，我們先來看一個(gè)例子

我們需要從一個(gè)二維矩陣中，搜索是否含有元素 7，我們?nèi)绾问褂枚植檎夷兀?/p>

其實(shí)我們可以完全將二維矩陣想象成一個(gè)有序的一維數(shù)組，然后再用二分，比如我們的二維矩陣中，共有 9 個(gè)元素，那定義我們的left = 0，right = 9 - 1= 8，是不是和一維數(shù)組定義相同，然后我們求我們的 mid 值， mid = left +（(right - left) >> 1）此時(shí) mid = 4 ，但是我們的二維矩陣下標(biāo)最大是，nums[2,2]呀，你這求了一個(gè) 4 ，讓我們怎么整呀。

如果我們理解了二分查找，那么這個(gè)題目考察我們的應(yīng)該是如何將一維數(shù)組的下標(biāo)，變?yōu)?二維坐標(biāo)。其實(shí)也很簡單，咱們看哈，此時(shí)咱們的 mid = 4，咱們的二維矩陣共有 3行， 3列，那我們 mid =4，肯定在第二行，那么這個(gè)應(yīng)該怎么求得呢?

我們可以直接用 （mid / 列數(shù)），即可，因?yàn)槲覀?mid = 4，4 /3 = 1,說明在第二行，那如果 mid = 7 ，7/3=2，在第三行，我們第幾行知道了，那么我們?nèi)绾沃赖趲琢心?？我們可以直接根?jù) （mid % 列數(shù) ）來求得呀，比如我們此時(shí) mid = 7，7%3 = 1，那么在我們一維數(shù)組索引為 7的元素（也就是10），其處于二維數(shù)組的第 3 行第 2 列，大家看看下圖是不是呀！

下面我們來看一下 leetcode 74題，讓我們給他整個(gè)通透

leetcode74搜索二維矩陣（中等）

題目描述

編寫一個(gè)高效的算法來判斷 m x n 矩陣中，是否存在一個(gè)目標(biāo)值。該矩陣具有如下特性：

每行中的整數(shù)從左到右按升序排列。每行的第一個(gè)整數(shù)大于前一行的最后一個(gè)整數(shù)。

示例1

輸入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,50]], target = 3 輸出：true

示例2

輸入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,50]], target = 13 輸出：false

示例3

輸入：matrix = [], target = 0 輸出：false

題目解析

在上面我們已經(jīng)解釋了如何在二維矩陣中進(jìn)行搜索，這里我們再對其進(jìn)行一個(gè)總結(jié)，就是我們憑空想象一個(gè)一維數(shù)組，這個(gè)數(shù)組是有二維數(shù)組一層一層拼接來的，也是完全有序，然后我們定義兩個(gè)指針一個(gè)指向一維數(shù)組頭部，一個(gè)指向尾部，我們求得 mid 值然后將 mid 變成二維坐標(biāo)，然后和 target 進(jìn)行比較，如果大于則移動(dòng) left ，如果小于則移動(dòng) right 。

動(dòng)圖解析

題目代碼

好啦 ，咱們的二分查找及其變種到這里就結(jié)束啦，希望通過這篇文章能讓大家掌握二分查找及其變種

責(zé)任編輯：xj

原文標(biāo)題：穿了好幾個(gè)馬甲，差點(diǎn)沒認(rèn)出來是二分查找

文章出處：【微信公眾號：算法與數(shù)據(jù)結(jié)構(gòu)】歡迎添加關(guān)注！文章轉(zhuǎn)載請注明出處。