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

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

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

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

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

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

問(wèn)題描述

來(lái)源：LeetCode第35題

難度：簡(jiǎn)單

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

請(qǐng)必須使用時(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 為無(wú)重復(fù)元素的升序排列數(shù)組

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

問(wèn)題分析

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

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

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

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

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

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

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

JAVA：

public int searchInsert(int[] nums, int target) {     int left = 0;// 左邊界，閉區(qū)間。     int right = nums.length;// 右邊界，開(kāi)區(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();// 右邊界，開(kāi)區(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

筆者簡(jiǎn)介

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