歡迎回到：遇見藍橋遇見你，不負代碼不負卿！

目錄

引入：二分查找

題目描述

題解

代碼執行

復雜度分析

例題一：搜索插入位置

題目描述

題解

代碼執行

復雜度分析

例題二：尋找峰值

題目描述

題解

代碼執行

復雜度分析

例題三：搜索二維矩陣

題目描述

題解

代碼執行

思考題

最大子序和

題目描述

代碼執行

藍橋結語：遇見藍橋遇見你，不負代碼不負卿！

好久不見啦鐵汁們，藍橋杯更新咯，快來嘗嘗鮮叭，

【前言】：由于本章基礎知識點不多，所以筆者直接講解四道典型題讓大家感受一下二分法的美妙，

準備開始咯，坐穩哈...

引入：二分查找

【敲黑板】：用二分演算法解題的前提是該陣列有序！！！

【注意】：查找一次砍掉一半，效率非常高！但是條件比較苛刻，一定要有序！

題目描述

給定一個 n 個元素有序的（升序）整型陣列 nums 和一個目標值 target ，寫一個函式搜索 nums 中的 target，如果目標值存在回傳下標，否則回傳 -1，

示例1：

輸入: nums = [-1,0,3,5,9,12], target = 9
輸出: 4
解釋: 9 出現在 nums 中并且下標為 4

示例2：

輸入: nums = [-1,0,3,5,9,12], target = 2
輸出: -1
解釋: 2 不存在 nums 中因此回傳 -1
 

題解

設定左右指標
找出中間位置，并判斷該位置值是否等于 target
nums[mid] == target 則回傳該位置下標
nums[mid] > target 則右側指標移到中間
nums[mid] < target 則左側指標移到中間

二分是一個比較簡單的演算法，只要大家記住上面這種套路就行啦，

代碼執行

int search(int* nums, int numsSize, int target){
    //考慮特殊情況
    if(nums == NULL || numsSize == 0){
        return -1;
    }
    int left = 0;//起始元素的索引
    int right = numsSize - 1;//末尾元素的索引
    int mid = 0;
    while(left <= right){
        //應該有很多人會寫成mid = (left + right) / 2;這種寫法不謹慎
        //因為做的是加法運算，所以要考慮溢位的特殊情況
        mid = left + (right - left) / 2;
        if(nums[mid] < target){
            left = mid + 1;
        }else if(nums[mid] > target){
            right = mid - 1;
        }else{
            return mid;
        }
    }
    return -1;
}

【注意】：while判斷運算式中是left <= right, 為什么還要加上left == right 的情況呢，當二者相等的時候說明還有一個元素需要被比較，所以當left > right時停下來，因為此時中間已經沒有元素需要被比較了，至于為什么將mid = left + (right - left) / 2; 的形式，上面代碼中已經講咯，

復雜度分析

時間復雜度：O(logN)

空間復雜度：O(1)

看，二分法是很高效的，大家在今后的訓練中，如果遇到查找搜索類的題目要求時間復雜度是O(logN)的，要想到二分法哦，

好嘞，這就是二分查找，是不是很簡單，下面再補充幾道典型例題，讓大家熟悉二分，

例題一：搜索插入位置

題目描述

給定一個排序陣列和一個目標值，在陣列中找到目標值，并回傳其索引，如果目標值不存在于陣列中，回傳它將會被按順序插入的位置，

請必須使用時間復雜度為 O(log n) 的演算法，

題目中要求使用時間復雜度為O(logN)的演算法解題，所以結合本題題意，很容易就想到了二分法，

示例1：

輸入: nums = [1,3,5,6], target = 5
輸出: 2

示例2：

輸入: nums = [1,3,5,6], target = 7
輸出: 4

題解

• 整體思路和普通的二分查找幾乎沒有區別，先設定左側下標 left 和右側下標 right，再計算中間下標 mid
• 每次根據 nums[mid] 和 target 之間的大小進行判斷，相等則直接回傳下標，nums[mid] < target 則 left 右移，nums[mid] > target 則 right 左移
• 查找結束如果沒有相等值則回傳 left，該值為插入位置,注意哦，最后如果沒有相等值，回傳的是left

【注意】：

二分查找的思路不難理解，但是邊界條件容易出錯，比如 回圈結束條件中 left 和 right 的關系，更新 left 和 right 位置時要不要加 1 減 1，這些都是大家自己動手畫圖理解，用代碼去體會，只可意會不可言傳哦，

代碼執行

int searchInsert(int* nums, int numsSize, int target){
    //考慮特殊情況
    if(nums == NULL || numsSize == 0){
        return -1;
    }
    int left = 0;
    int right = numsSize - 1;
    int mid = 0;
    while(left <= right){
        mid = left + (right - left) / 2;
        if(nums[mid] > target){
            right = mid - 1;
        }else if(nums[mid] < target){
            left = mid + 1;
        }else{
            return mid;
        }
    }
    return left;
}

復雜度分析

時間復雜度：O(logN)

空間復雜度：O(1)

是不是很簡單，下面開始蹭加點難度咯，有點繞，需要仔細想哦，加油加油，

例題二：尋找峰值

題目描述

峰值元素是指其值嚴格大于左右相鄰值的元素，

給你一個整數陣列 nums，找到峰值元素并回傳其索引，陣列可能包含多個峰值，在這種情況下，回傳 任何一個峰值 所在位置即可，

你可以假設 nums[-1] = nums[n] = -∞ ，

你必須實作時間復雜度為 O(log n) 的演算法來解決此問題，

示例1：

輸入：nums = [1,2,3,1]
輸出：2
解釋：3 是峰值元素，你的函式應該回傳其索引 2，

示例2：

輸入：nums = [1,2,1,3,5,6,4]
輸出：1 或 5 
解釋：你的函式可以回傳索引 1，其峰值元素為 2；
     或者回傳索引 5， 其峰值元素為 6，

題解

【注意】：二分法解題的前提要求是有序的，這題看起來沒說有序呀，那怎么還能用二分法呢，我們也不能先進行排序，因為會把索引打亂，那該怎么辦呢，請朝后看...

描述這個規律就是：

• 規律一：如果nums[mid] > nums[mid+1]，則在mid之前一定存在峰值元素
• 規律二：如果nums[mid] < nums[mid+1]，則在mid+1之后一定存在峰值元素

代碼執行

int findPeakElement(int* nums, int numsSize){
    //考慮特殊情況
    if(nums == NULL || numsSize == 0){
        return -1;
    }
    int left = 0;
    int right = numsSize - 1;
    int mid = 0;
    while(left <= right){
        if(left == right){
            return left;
        }
        mid = left + (right - left) / 2;
        if(nums[mid] > nums[mid + 1]){
            right = mid;//mid之前一定存在峰值元素
        }else{
            left = mid + 1;//mid+1之后一定存在峰值元素
        }
    }
    return left;
}

復雜度分析

時間復雜度：O(logN)

空間復雜度：O(1)

例題三：搜索二維矩陣

題目描述

撰寫一個高效的演算法來判斷 m x n 矩陣中，是否存在一個目標值，該矩陣具有如下特性：

每行中的整數從左到右按升序排列，
每行的第一個整數大于前一行的最后一個整數，

也就是說，整個二維陣列都是升序的，

示例1：

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

示例2：

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

題解

【注意】：本題的重點就在于一維索引和二維索引間的互換

代碼執行

bool searchMatrix(int** matrix, int matrixSize, int* matrixColSize, int target){
    //考慮特殊情況
    if(matrix == NULL || matrixSize == 0){
        return false;
    }
    int row = matrixSize;//行數
    int col = *matrixColSize;//列數
    int left = 0;//起始元素的索引
    int right = row * col - 1;//最后一個元素的索引
    int mid = 0;
    int element = 0;
    while(left <= right){
        mid = left + (right - left) / 2;
        element = matrix[mid / col][mid % col];//將一維的索引化成二維的索引
        if(element == target){
            return true;
        }else if(element > target){
            right = mid - 1;
        }else{
            left = mid + 1;
        }
    }
    return false;
}

復雜度分析

時間復雜度：O(logN)

空間復雜度：O(1)

好嘍，鐵汁把上面四道題目練習一遍，肯定就能對二分演算法有一定的認識，加油加油哦，

思考題

大家先將上篇博文（分治演算法）看一下，現在講解那道留下的思考題，

藍橋杯演算法競賽系列第三章——細談遞回的bro分治_安然無虞的博客-CSDN博客

最大子序和

題目描述

給定一個整數陣列，找到一個具有最大和的連續子陣列（子陣列中至少包含一個數），要求回傳其最大和，

注意：本題要求的是連續的子陣列，可能有的題目要求可以是斷開的，但本題不是，

將陣列nums由中點mid分為三種情況：

1. 最大子串在左邊

2. 最大子串在右邊

3. 最大子串跨中點，左右兩邊元素都有（理解上的難點）

lSum 表示 [l,r] 內以 l 為左端點的最大子段和
rSum 表示 [l,r] 內以 r 為右端點的最大子段和
mSum 表示 [l,r] 內的最大子段和
iSum 表示 [l,r] 的區間和

代碼執行

struct Status {
    int lSum, rSum, mSum, iSum;
};

struct Status pushUp(struct Status l, struct Status r) {
    int iSum = l.iSum + r.iSum;
    int lSum = fmax(l.lSum, l.iSum + r.lSum);
    int rSum = fmax(r.rSum, r.iSum + l.rSum);
    int mSum = fmax(fmax(l.mSum, r.mSum), l.rSum + r.lSum);
    return (struct Status){lSum, rSum, mSum, iSum};
};

struct Status get(int* a, int l, int r) {
    if (l == r) {
        return (struct Status){a[l], a[l], a[l], a[l]};
    }
    int m = l + (r - l) / 2;
    struct Status lSub = get(a, l, m);
    struct Status rSub = get(a, m + 1, r);
    return pushUp(lSub, rSub);
}

int maxSubArray(int* nums, int numsSize) {
    return get(nums, 0, numsSize - 1).mSum;
}

由于想讓大家搞懂知識點，所以這里的題目可能用這種解法不是最優解，沒關系，我會在后面的演算法中補充到，在每日一題中也會涉及到，今天就不布置思考題咯，鐵汁們好好把上面題目自己嘗試做出來，

藍橋結語：遇見藍橋遇見你，不負代碼不負卿！

嘿嘿，期待鐵汁們留言點評，如果能夠再動動小手，給博主來個三連那就更好啦，您的認可就是我最大的動力！求求啦~~