專欄：50多種數(shù)據(jù)結(jié)構(gòu)徹底征服

專欄：50多種經(jīng)典圖論算法全部掌握

有消息稱字節(jié)跳動以4-2的職級和8位數(shù)的年包工資挖走原阿里通義大模型技術(shù)負(fù)責(zé)人周暢。周暢于2017年入職阿里，曾擔(dān)任阿里通義大模型技術(shù)負(fù)責(zé)人。去年7月周暢離職后，已于8月加入字節(jié)，從事AI大模型相關(guān)工作。

據(jù)第一財經(jīng)報道稱，“來字節(jié)的不止周暢一個人，他手底下的團(tuán)隊還有十多個人也跟著跳槽了。”字節(jié)給周暢提供了一份幾乎無法拒絕的合同：4-2的職級和8位數(shù)的年包工資，按阿里的職級體系換算大約是連跳兩級且薪資翻好幾倍。與他一起來的原團(tuán)隊成員，字節(jié)也都給了4-1、3-2（對標(biāo)阿里級別P10、P9）的職級。

--------------下面是今天的算法題--------------

來看下今天的算法題，這題是LeetCode的第35題：搜索插入位置。

問題描述

來源：LeetCode第35題

難度：簡單

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

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

示例1：

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

示例2：

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

• 1 <= nums.length <= 10^4

• -10^4 <= nums[i] <= 10^4

• nums 為無重復(fù)元素的升序排列數(shù)組

• -10^4 <= target <= 10^4

問題分析

這題讓查找目標(biāo)值在數(shù)組中的位置，如果沒找到就返回目標(biāo)值應(yīng)該插入的位置，這是一道典型的二分查找題。對于二分查找可以使用 左閉右閉 和 左閉右開 兩種方式，無論哪種方式都要注意防止出現(xiàn)死循環(huán)。

防止出現(xiàn)死循環(huán)的判斷也比較簡單，就是無論是開區(qū)間還是閉區(qū)間， 每次 while 循環(huán)的時候，兩個指針必須要有一個指針的值發(fā)生改變 。我們這里就以 左閉右開 區(qū)間來分析下，解題步驟如下：

1，使用兩個指針一個指向查詢區(qū)域的左端 left ，一個指向查詢區(qū)域右端的下一個位置 right ，每次取區(qū)域內(nèi) [left，right) 中間位置的值。

2，如果目標(biāo)值等于中間值，說明找到了，直接返回 mid 。

3，如果目標(biāo)值大于中間值，說明中間值及前面部分太小了，下一步需要往后半部分查找 [mid+1,right) 。

4，如果目標(biāo)值小于中間值，說明中間值及后面部分太大了，但中間值有可能是需要插入的位置，所以中間值的位置不能排除，下一步需要往前半部分查找 [left,mid) 。

因為 right 是開區(qū)間，當(dāng) left >= right 的時候說明查詢區(qū)間為空，終止循環(huán)，所以循環(huán)執(zhí)行的條件是 left < right 。

JAVA：

public int searchInsert(int[] nums, int target) {     int left = 0;// 左邊界，閉區(qū)間。     int right = nums.length;// 右邊界，開區(qū)間。     while (left < right) {         int mid = (left + right) >>> 1;// 中間值。         if (nums[mid] == target)             return mid;         else if (nums[mid] < target) {             left = mid + 1; // 縮小范圍到[mid+1,right]         } else {// if (nums[mid] > target)             right = mid;  // 縮小范圍到[left,mid)         }     }     return right;// 或者return left; }

C++：

public:     int searchInsert(vector

 & nums, int target) {         int left = 0;// 左邊界，閉區(qū)間。         int right = nums.size();// 右邊界，開區(qū)間。         while (left < right) {             int mid = left + (right-left)/2 ;// 中間值。             if (nums[mid] == target)                 return mid;             else if (nums[mid] < target) {                 left = mid + 1; // 縮小范圍到[mid+1,right]             } else {// if (nums[mid] > target)                 right = mid;  // 縮小范圍到[left,mid)             }         }         return right;// 或者return left;     }

Python：

def searchInsert(self, nums: List[int], target: int) -> int:     left, right = 0, len(nums)     while left < right:         mid = (left + right) // 2         if nums[mid] == target:             return mid         elif nums[mid] < target:             left = mid + 1  # 縮小范圍到[mid+1, right]         else:  # if (nums[mid] > target)             right = mid  # 縮小范圍到[left, mid)     return right

筆者簡介

博哥，真名：王一博，畢業(yè)十多年， 作者，專注于 數(shù)據(jù)結(jié)構(gòu)和算法 的講解，在全球30多個算法網(wǎng)站中累計做題2000多道，在公眾號中寫算法題解800多題，對算法題有自己獨特的解題思路和解題技巧，喜歡的可以給個關(guān)注，也可以 下載我整理的1000多頁的PDF算法文檔 。