今天給大家?guī)?lái)的是二分查找及其變種的總結(jié),，大家一定要看到最后呀,，用心滿滿,，廢話不多說(shuō)，讓導(dǎo)演幫我們把鏡頭切到袁記菜館吧,！

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

店小二：掌柜的，您進(jìn)貨回來(lái)了呀,，喲,！今天您買(mǎi)這魚(yú)挺大呀！

袁廚：那是,，這是我今天從咱們江邊買(mǎi)的,，之前一直去菜市場(chǎng)買(mǎi)，那里的老貴了,，你猜猜我今天買(mǎi)的多少錢(qián)一條,。

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

袁廚：貴了。

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

袁廚：還是貴了。

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

袁廚：便宜了

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

袁廚：恭喜你猜對(duì)了

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

二分查找

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

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

下面我們通過(guò)一個(gè)例子來(lái)幫助我們理解。我們需要在 nums 數(shù)組中,，查詢?cè)?8 的索引

int[ ]  nums = {1,3,4,5,6,8,12,14,16}; target = 8  

（1）我們需要定義兩個(gè)指針?lè)謩e指向數(shù)組的頭部及尾部,，這是我們?cè)谡麄€(gè)數(shù)組中查詢的情況，當(dāng)我們?cè)跀?shù)組

某一區(qū)間進(jìn)行查詢時(shí),，可以輸入數(shù)組,，起始位置，終止位置進(jìn)行查詢,。

（2）找出mid,，該索引為 mid =（left + right）/ 2,，但是這樣寫(xiě)有可能溢出，所以我們需要改進(jìn)一下寫(xiě)成

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 指針,，見(jiàn)下圖

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

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

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

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

則返回,。

2.如果 nums[mid] 和 target 不相等,，則對(duì) nums[mid] 和 target 值進(jìn)行比較大小,，通過(guò)比較結(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)圖解析

下面我們來(lái)看一下二分查找的代碼,，可以認(rèn)真思考一下 if 語(yǔ)句的條件,，每個(gè)都沒(méi)有簡(jiǎn)寫(xiě),。

 public static int binarySearch(int[] nums,int target,int left, int right) {
        //這里需要注意，循環(huán)條件
        while (left <= right) {
            //這里需要注意,，計(jì)算mid
            int mid = left + ((right - left) >> 1);
            if (nums[mid] == target) {
                return mid;
            }else if (nums[mid] < target) {
                //這里需要注意,，移動(dòng)左指針
                left  = mid + 1;
            }else if (nums[mid] > target) {
                //這里需要注意，移動(dòng)右指針
                right = mid - 1;
            }
        }
        //沒(méi)有找到該元素,，返回 -1
        return -1;
    }

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

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

2.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)

3.left = mid + 1,right = mid - 1 而不是 left = mid 和 right = mid,。我們思考一下這種情況,見(jiàn)下圖,，當(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 。

下面我們來(lái)看一下二分查找的遞歸寫(xiě)法

public static int binarySearch(int[] nums,int target,int left, int right) {
        
        if (left <= right) {
            int mid = left + ((right - left) >> 1);
            if (nums[mid] == target) {
                //查找成功
                return  mid;
            }else if (nums[mid] > target) {
                //新的區(qū)間,左半?yún)^(qū)間
                return binarySearch(nums,target,left,mid-1);
            }else if (nums[mid] < target) {
                //新的區(qū)間,，右半?yún)^(qū)間
                return binarySearch(nums,target,mid+1,right);
            }
        }
        //不存在返回-1
        return -1;
    }

例題：

題目描述

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

你可以假設(shè)數(shù)組中無(wú)重復(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è)題目完全就和咱們的二分查找一樣,，只不過(guò)有了一點(diǎn)改寫(xiě)，那就是將咱們的返回值改成了 left,，具體實(shí)現(xiàn)過(guò)程見(jiàn)下圖

class Solution {
    public int searchInsert(int[] nums, int target) {

        int left = 0, right = nums.length-1;
        //注意循環(huán)條件
        while (left <= right) {
            //求mid
            int mid = left + ((right - left ) >> 1);
            //查詢成功
            if (target == nums[mid]) {
                return mid;
            //右區(qū)間    
            } else if (nums[mid] < target) {
                left = mid + 1;   
            //左區(qū)間               
            } else if (nums[mid] > target) {
                right = mid - 1;
            }
        }
        //返回插入位置
        return left;
    }
}

二分查找變種一

上面我們說(shuō)了如何使用二分查找在數(shù)組或區(qū)間里查出特定值的索引位置,。但是我們剛才數(shù)組里面都沒(méi)有重復(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è)文章的主題就是二分查找,，我們可不可以用二分查找來(lái)實(shí)現(xiàn)呢,？當(dāng)然是可以的。

題目描述

給定一個(gè)按照升序排列的整數(shù)數(shù)組 nums,，和一個(gè)目標(biāo)值 target,。找出給定目標(biāo)值在數(shù)組中的開(kāi)始位置和結(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(shuō)了如何使用遍歷解決該題,，但是這個(gè)題目的目的就是讓我們使用二分查找,，我們來(lái)逐個(gè)分析，先找出目標(biāo)元素的下邊界,，那么我們?nèi)绾握业侥繕?biāo)元素的下邊界呢,？

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

  if (nums[mid] == target) {
       return mid;
  }else if (nums[mid] < target) {
      //這里需要注意，移動(dòng)左指針
      left  = mid + 1;
  }else if (nums[mid] > target) {
      //這里需要注意,，移動(dòng)右指針
      right = mid - 1;
  } 

我們只需在這段代碼中修改即可,，我們?cè)賮?lái)剖析一下這塊代碼，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)槲覀円?/p>

的是數(shù)的下邊界,，所以我們需要在 mid 的值的左區(qū)間繼續(xù)尋找 5 ,，那我們應(yīng)該怎么做呢？我們只需在

target <= nums[mid] 時(shí),，讓 right = mid - 1即可,，這樣我們就可以繼續(xù)在 mid 的左區(qū)間繼續(xù)找 5 。是不是聽(tīng)著有點(diǎn)繞,，我們通過(guò)下面這組圖進(jì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í)我們的下邊界,。我們來(lái)看一下求下邊界的具體執(zhí)行過(guò)程,。

動(dòng)圖解析

計(jì)算下邊界代碼

int lowerBound(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            //這里需要注意，計(jì)算mid
            int mid = left + ((right - left) >> 1);
            if (target <= nums[mid]) {
                //當(dāng)目標(biāo)值小于等于nums[mid]時(shí),，繼續(xù)在左區(qū)間檢索,，找到第一個(gè)數(shù)
                right = mid - 1;

            }else if (target > nums[mid]) {
                //目標(biāo)值大于nums[mid]時(shí)，則在右區(qū)間繼續(xù)檢索,，找到第一個(gè)等于目標(biāo)值的數(shù)
                left = mid + 1;

            }
        }
        return left;
    }

計(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ì)算上邊界代碼

int upperBound(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            //求mid
            int mid = left + ((right - left) >> 1);
            //移動(dòng)左指針情況
            if (target >= nums[mid]) {
                 left = mid + 1; 
            //移動(dòng)右指針情況
            }else if (target < nums[mid]) {
                right = mid - 1;
            }
            
        }
        return left;
    }

題目完整代碼

class Solution {
    public int[] searchRange (int[] nums, int target) {
         int upper = upperBound(nums,target);
         int low = lowerBound(nums,target);  
         //不存在情況
         if (upper < low) {
             return new int[]{-1,-1};
         }
         return new int[]{low,upper};
    }
    //計(jì)算下邊界
    int lowerBound(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            //這里需要注意，計(jì)算mid
            int mid = left + ((right - left) >> 1);
            if (target <= nums[mid]) {
                //當(dāng)目標(biāo)值小于等于nums[mid]時(shí),，繼續(xù)在左區(qū)間檢索,，找到第一個(gè)數(shù)
                right = mid - 1;

            }else if (target > nums[mid]) {
                //目標(biāo)值大于nums[mid]時(shí)，則在右區(qū)間繼續(xù)檢索，找到第一個(gè)等于目標(biāo)值的數(shù)
                left = mid + 1;

            }
        }
        return left;
    }
    //計(jì)算上邊界
    int upperBound(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {          
            int mid = left + ((right - left) >> 1);
            if (target >= nums[mid]) {
                 left = mid + 1;               
            }else if (target < nums[mid]) {
                right = mid - 1;
            }            
        }
        return right;
    }
}

二分查找變種二

我們?cè)谏厦娴淖兎N中,，描述了如何找出目標(biāo)元素在數(shù)組中的上下邊界,，然后我們下面來(lái)看一個(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)了解，下面我們先來(lái)看一下如何在數(shù)組或區(qū)間中找出第一個(gè)大于目標(biāo)元素的數(shù)吧,。

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

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

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

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

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

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

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è)變種給整的明明白白的了，下面我們看一哈程序代碼吧,，也是非常簡(jiǎn)單的,。

public static int lowBoundnum(int[] nums,int target,int left, int right) {

        while (left <= right) {
            //求中間值
            int mid = left + ((right - left) >> 1);
            //大于目標(biāo)值的情況
            if (nums[mid] > target) {
                 //返回 mid
                if (mid == 0 || nums[mid-1] <= target) {
                    return mid;
                }
                else{
                    right = mid -1;
                }

            } else if (nums[mid] <= target){
                left = mid + 1;
            }
        }
        //所有元素都小于目標(biāo)元素
        return -1;
    }

通過(guò)上面的例子我們應(yīng)該可以完全理解了那個(gè)變種，下面我們繼續(xù)來(lái)看以下這種情況,，那就是如何找到最后一個(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è)也完全可以搞定了，下面我們看一下代碼吧,。

public static int upperBoundnum(int[] nums,int target,int left, int right) {

        while (left <= right) {

            int mid = left + ((right - left) >> 1);
             //小于目標(biāo)值
            if (nums[mid] < target) {
                //看看是不是當(dāng)前區(qū)間的最后一位,，如果當(dāng)前小于，后面一位大于,，返回當(dāng)前值即可
                if (mid == right || nums[mid+1] >= target) {
                    return mid;
                }
                else{
                    left = mid + 1;
                }

            } else if (nums[mid] >= target){
                right = mid - 1;
            }
        }
        //沒(méi)有查詢到的情況
        return -1;
    }

哎嘛寫(xiě)著寫(xiě)著咋就那么多了,，太長(zhǎng)了大家就不愛(ài)看啦，剩下的就放在下篇吧,，咱們下篇見(jiàn)呀,！