當前位置：首頁 > news >正文

青島專業(yè)網站制作團隊肇慶百度快照優(yōu)化

news 2025/7/3 7:26:11

青島專業(yè)網站制作團隊,肇慶百度快照優(yōu)化,哪個網站能上傳自己做的簡歷,網站開發(fā) 后端服務目錄二分查找算法原理 ①力扣704. 二分查找解析代碼 ②力扣34. 在排序數組中查找元素的第一個和最后一個位置解析代碼 ③力扣69. x 的平方根解析代碼 ④力扣35. 搜索插入位置解析代碼 ⑤力扣852. 山脈數組的峰頂索引解析代碼 ⑥力扣162. 尋找峰值解析代碼…

二分查找算法原理

①力扣704. 二分查找

解析代碼

②力扣34. 在排序數組中查找元素的第一個和最后一個位置

解析代碼

③力扣69. x 的平方根?

解析代碼

④力扣35. 搜索插入位置

解析代碼

⑤力扣852. 山脈數組的峰頂索引

解析代碼

⑥力扣162. 尋找峰值

解析代碼

⑦力扣153. 尋找旋轉排序數組中的最小值

解析代碼

⑧力扣LCR 173. 點名

解析代碼

本篇完。

二分查找算法原理

????????二分查找一種效率較高的查找方法。已經有嚴謹的數學證明其時間復雜度是O（logN），如果在全國14億人口中找一個人，那么只需查找31次，但是，二分查找要求線性表必須采用順序存儲結構，而且表中元素按關鍵字有序排列（無序有時也行，但是要有二段性）。一般步驟如下：

????????首先，假設表中元素是按升序排列，將表中間位置記錄的關鍵字與查找關鍵字比較，如果兩者相等，則查找成功；否則利用中間位置記錄將表分成前、后兩個子表，如果中間位置記錄的關鍵字大于查找關鍵字，則進一步查找前一子表，否則進一步查找后一子表。重復以上過程，直到找到滿足條件的記錄，使查找成功，或直到子表不存在為止，此時查找不成功。

以前學C/C++也寫過二分查找的代碼，直接刷題：

①力扣704. 二分查找

704. 二分查找 - 力扣（LeetCode）

難度簡單

給定一個?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

提示：

你可以假設?nums?中的所有元素是不重復的。
n?將在?[1, 10000]之間。
nums?的每個元素都將在?[-9999, 9999]之間。

class Solution {
public:int search(vector<int>& nums, int target) {}
};

解析代碼

首先是有序的，就知道用二分，且這是一道樸素的二分（后面有不樸素的），簡單題重拳出擊：

class Solution {
public:int search(vector<int>& nums, int target) {int left = 0, right = nums.size() - 1;while(left <= right){int mid = left + (right - left) / 2;if(nums[mid] > target){right = mid - 1;}else if(nums[mid] < target){left = mid + 1;}else{return mid;}}return -1;}
};

②力扣34. 在排序數組中查找元素的第一個和最后一個位置

34. 在排序數組中查找元素的第一個和最后一個位置 - 力扣（LeetCode）

難度中等

給你一個按照非遞減順序排列的整數數組?nums，和一個目標值?target。請你找出給定目標值在數組中的開始位置和結束位置。

如果數組中不存在目標值?target，返回?[-1, -1]。

你必須設計并實現時間復雜度為?O(log n)?的算法解決此問題。

示例 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]

提示：

0 <= nums.length <= 10^5
-10^9?<= nums[i]?<= 10^9
nums?是一個非遞減數組
-10^9?<= target?<= 10^9

class Solution {
public:vector<int> searchRange(vector<int>& nums, int target) {}
};

解析代碼

非遞減，就是數組往后都是大于或者等于的元素，用暴力解法就是找到隨便一個端點元素，然后往前往后線性遍歷，極端時間復雜度還是O（N），這里用進階二分的套路（等下總結）

class Solution {
public:vector<int> searchRange(vector<int>& nums, int target) {int size = nums.size();if(size == 0) // 處理邊界return {-1, -1}; //返回一個vector里兩個整數的方式int left = 0, right = size - 1; // 找左端點while(left < right) // 一定是小于{int mid = left + (right - left) / 2; // 元素個數是偶數時，中點是中間的左邊if(nums[mid] < target) // 左端點肯定不在左邊left = mid + 1;elseright = mid; // 可能自己是左端點，可能左端點還在左邊}if(nums[left] != target) // 沒有端點的情況return {-1, -1};int tmp = left; // 記錄左端點right = size - 1; // 找右端點，left不用重置while(left < right){int mid = left + (right - left + 1) / 2; // 元素個數是偶數時，中點是中間的右邊if(nums[mid] > target) // 右端點肯定右在左邊right = mid -1;elseleft = mid; // 可能自己是右端點，可能右端點還在右邊}return {tmp, right};}
};

以后二分大部分題目都是這個進階二分的套路，套路就是這樣的了（注意兩個while的比較）：

        int left = 0, right = size - 1; // 找左端點while(left < right) // 一定是小于{int mid = left + (right - left) / 2; // 元素個數是偶數時，中點是中間的左邊if(nums[mid] < target) // 左端點肯定不在左邊left = mid + 1;elseright = mid; // 可能自己是左端點，可能左端點還在左邊}if(nums[left] != target) // 沒有端點的情況return {-1, -1};int tmp = left; // 記錄左端點right = size - 1; // 找右端點，left不用重置while(left < right){int mid = left + (right - left + 1) / 2; // 元素個數是偶數時，中點是中間的右邊if(nums[mid] > target) // 右端點肯定右在左邊right = mid -1;elseleft = mid; // 可能自己是右端點，可能右端點還在右邊}return {tmp, right};

③力扣69. x 的平方根?

69. x 的平方根 - 力扣（LeetCode）

難度簡單

給你一個非負整數?x?，計算并返回?x?的?算術平方根?。

由于返回類型是整數，結果只保留?整數部分?，小數部分將被?舍去。

注意：不允許使用任何內置指數函數和算符，例如?pow(x, 0.5)?或者?x ** 0.5?。

示例 1：

輸入：x = 4
輸出：2

示例 2：

輸入：x = 8
輸出：2
解釋：8 的算術平方根是 2.82842..., 由于返回類型是整數，小數部分將被舍去。

提示：

0 <= x <= 2^31 - 1

class Solution {
public:int mySqrt(int x) {}
};

解析代碼

暴力解法可以遍歷1到X / 2的所有整數，因為這段整數是有序的，所有可以用二分算法，用上一題力扣34總結的進階二分套路，求右端點：

class Solution {
public:int mySqrt(int x) {if(x <= 1) // 看給的范圍處理邊界{return x / 1; // 如果是1的話下面right就是0了}int left = 0, right = x / 2;while(left < right){long long mid = left + (right - left + 1) / 2;if(mid * mid > x) // 開long long防溢出{right = mid - 1;}else{left = mid;}}return right;}
};

④力扣35. 搜索插入位置

35. 搜索插入位置 - 力扣（LeetCode）

難度簡單

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

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

示例 1:

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

示例?2:

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

示例 3:

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

提示:

1 <= nums.length <= 10^4
-10^4 <= nums[i] <= 10^4
nums?為?無重復元素?的?升序?排列數組
-10^4 <= target <= 10^4

class Solution {
public:int searchInsert(vector<int>& nums, int target) {}
};

解析代碼

明顯的二分查找，且找左端點：

class Solution {
public:int searchInsert(vector<int>& nums, int target) {int left = 0, right = nums.size() - 1;if(nums[right] < target) // 找不到就尾插{return right + 1;}while(left < right) // 找不到target就找一個比target大的值，插入到它的前面{int mid = left + (right - left) / 2; // 根據上面注釋用二分中找左端點的套路if(nums[mid] < target){left = mid + 1;}else{right = mid;}}return left; // 找沒找到都是返回left下標}
};

⑤力扣852. 山脈數組的峰頂索引

852. 山脈數組的峰頂索引 - 力扣（LeetCode）

LCR 069. 山脈數組的峰頂索引 - 力扣（LeetCode）

難度中等

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

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

示例 1:

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

示例?2:

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

示例 3:

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

提示:

1 <= nums.length <= 10^4
-10^4 <= nums[i] <= 10^4
nums?為?無重復元素?的?升序?排列數組
-10^4 <= target <= 10^4

class Solution {
public:int searchInsert(vector<int>& nums, int target) {}
};

解析代碼

雖然整個數組不是有序的，但是根據單調性可以分出二段性。這里利用二段性把mid歸到遞增部分，下面就是找右端點：

class Solution {
public:int peakIndexInMountainArray(vector<int>& arr) {// 雖然整個數組不是有序的，但是根據單調性可以分出二段性// 這里利用二段性把mid歸到遞增部分，下面就是找右端點：int left = 0, right = arr.size() - 1;while(left < right){int mid = left + (right - left + 1) / 2;if(arr[mid] < arr[mid - 1]) // 如果是遞減部分{right = mid - 1;}else{left = mid;}}return left;}
};

⑥力扣162. 尋找峰值

162. 尋找峰值 - 力扣（LeetCode）

難度中等

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

給你一個整數數組?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。

提示：

1 <= nums.length <= 1000
-2^31 <= nums[i] <= 2^31 - 1

class Solution {
public:int findPeakElement(vector<int>& nums) {}
};

解析代碼

????????注意到是返回任意個峰值都可以，就類似數學的求極大值，那問題就變成上一題力扣852. 山脈數組的峰頂索引了，直接把nums參數改成arr然后復制上一題代碼過來就AC了，二段性就是如果找到一個點，如果這個點的右邊元素比它小，那么一定有一個極大值在它左邊。反之極大值在它右邊或者它就是極大值。

class Solution {
public:int findPeakElement(vector<int>& arr) {// 雖然整個數組不是有序的，但是根據單調性可以分出二段性// 這里利用二段性把mid歸到遞增部分，下面就是找右端點：int left = 0, right = arr.size() - 1;while(left < right){int mid = left + (right - left + 1) / 2;if(arr[mid] < arr[mid - 1]) // 如果是遞減部分{right = mid - 1;}else{left = mid;}}return left;}
};

⑦力扣153. 尋找旋轉排序數組中的最小值

153. 尋找旋轉排序數組中的最小值 - 力扣（LeetCode）

難度中等

已知一個長度為?n?的數組，預先按照升序排列，經由?1?到?n?次?旋轉?后，得到輸入數組。例如，原數組?nums = [0,1,2,4,5,6,7]?在變化后可能得到：

若旋轉?4?次，則可以得到?[4,5,6,7,0,1,2]
若旋轉?7?次，則可以得到?[0,1,2,4,5,6,7]

注意，數組?[a[0], a[1], a[2], ..., a[n-1]]?旋轉一次?的結果為數組?[a[n-1], a[0], a[1], a[2], ..., a[n-2]]?。

給你一個元素值?互不相同?的數組?nums?，它原來是一個升序排列的數組，并按上述情形進行了多次旋轉。請你找出并返回數組中的?最小元素?。

你必須設計一個時間復雜度為?O(log n)?的算法解決此問題。

示例 1：

輸入：nums = [3,4,5,1,2]
輸出：1
解釋：原數組為 [1,2,3,4,5] ，旋轉 3 次得到輸入數組。

示例 2：

輸入：nums = [4,5,6,7,0,1,2]
輸出：0
解釋：原數組為 [0,1,2,4,5,6,7] ，旋轉 3 次得到輸入數組。

示例 3：

輸入：nums = [11,13,15,17]
輸出：11
解釋：原數組為 [11,13,15,17] ，旋轉 4 次得到輸入數組。

提示：

n == nums.length
1 <= n <= 5000
-5000 <= nums[i] <= 5000
nums?中的所有整數?互不相同
nums?原來是一個升序排序的數組，并進行了?1?至?n?次旋轉

class Solution {
public:int findMin(vector<int>& nums) {}
};

解析代碼

?二段性就是以最右邊元素（下圖為D）為標志，如果一個點比它大，那么找的元素肯定在另一邊，

以A為標志也行，但是有邊界情況要處理，下面就以D為標志，找左端點：

class Solution {
public:int findMin(vector<int>& nums) {// 二段性就是以最右邊元素為標志，如果一個點比它大，那么找的元素肯定在另一邊// 以下就是二分找左端點的套路int left = 0, right = nums.size() - 1;int tmp = right;while(left < right){int mid = left + (right - left) / 2;if(nums[mid] > nums[tmp]) // 如果是遞減部分{left = mid + 1;}else{right = mid;}}return nums[left];}
};

⑧力扣LCR 173. 點名

LCR 173. 點名 - 力扣（LeetCode）

難度簡單

某班級 n 位同學的學號為 0 ~ n-1。點名結果記錄于升序數組?records。假定僅有一位同學缺席，請返回他的學號。

示例 1:

輸入: records = [0,1,2,3,5]
輸出: 4

示例?2:

輸入: records = [0, 1, 2, 3, 4, 5, 6, 8]
輸出: 7

提示：

1 <= records.length?<= 10000

class Solution {
public:int takeAttendance(vector<int>& records) {}
};

解析代碼

此題就是以前寫過的劍指Offer中數組消失的數字，解法有哈希，遍歷，位運算，數學求和，時間都是O（N），二分的解法是O（logN）。

二段性就是找的元素的值肯定不等于數組下標，求左端點的套路：

class Solution {
public:int takeAttendance(vector<int>& records) {// 解法有哈希，遍歷，位運算，數學求和，時間都是O（N），二分的解法是O（logN）// 此題二段性就是找的元素的值肯定不等于數組下標，求左端點的套路int left = 0, right = records.size() - 1;if(records[right] == right){return right + 1;}while(left < right){int mid = left + (right - left) / 2;if(records[mid] == mid){left = mid + 1;}else{right = mid;}}return records[left] - 1;}
};