作者：reed，一個熱愛技術的斜杠青年，程序員面試聯合創始人

前文回顧：

leetcode1. 兩數之和--每天刷一道leetcode系列！

leetcode2. 兩數相加--每天刷一道leetcode系列！

leetcode3. 無重復字符的最長子串--每天刷一道leetcode系列！

leetcode4. 尋找兩個有序數組的中位數--每天刷一道leetcode系列！

leetcode5.最長回文子串--每天刷一道leetcode系列!

leetcode9. 回文數--每天刷一道leetcode系列！

leetcode11. 盛最多水的容器--每天刷一道leetcode系列！

leetcode14. 最長公共前綴--每天刷一道leetcode算法題系列！

leetcode15. 三數之和--每天刷一道leetcode算法系列！

leetcode16. 最接近的三數之和--每天刷一道leetcode算法系列！

leetcode17. 電話號碼的字母組合--每天刷一道leetcode算法系列！

leetcode18. 四數之和--每天刷一道leetcode算法系列！

leetcode19. 刪除鏈表的倒數第N個節點--每天刷一道leetcode算法系列！

leetcode20. 括號生成--每天刷一道leetcode算法系列！

leetcode21. 合并兩個有序鏈表--每天刷一道leetcode算法系列！

leetcode22. 括號生成--每天刷一道leetcode算法系列！

leetcode23. 合并K個排序鏈表--每天刷一道leetcode算法系列！

leetcode24. 兩兩交換鏈表中的節點--每天刷一道leetcode算法系列！

leetcode25. K個一組翻轉鏈表--每天刷一道leetcode算法系列！

leetcode26. 刪除排序數組中的重復項--每天刷一道leetcode算法系列!

leetcode27. 移除元素--每天刷一道leetcode算法系列！

leetcode32. 最長有效括號--每天刷一道leetcode算法系列！

leetcode33. 搜索旋轉排序數組--每天刷一道leetcode算法系列！

leetcode 34. 在排序數組中查找元素的第一個和最后一個位置--每天刷一道leetcode算法系列！(本篇)

題目描述

給定一個按照升序排列的整數數組 nums，和一個目標值 target。找出給定目標值在數組中的開始位置和結束位置。
你的算法時間復雜度必須是 O(log n) 級別。
如果數組中不存在目標值，返回 [-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]

分析

本題是一個典型的二分查找類題目。題目的意思很明確，就是尋找左邊界和右邊界。
二分查找看似很簡單，其實里面的變化還是蠻多的。
如何尋找左邊界呢？
1.1如果nums[mid] < target，那么左邊沒有target。start = mid+1，?

1.2如果nums[mid]==target，在正常的二分查找中，這種情況是可以直接返回結果。但是因為我們是要查找左邊界，這就有可能mid的左邊還有可能有target這個數。因此需要進行兩步操作。??

1.2.1 用一個變量res標記mid的值，如果左邊還有數值等于target，則更新res的值。否則直接返回res即可。??

1.2.2 end = mid - 1，繼續向左查找。

1.3 如果nums[mid] > target, 同1.2.2 end = mid - 1，繼續向左查找。

如何尋找右邊界呢？
2.1如果nums[mid] > target，那么右邊沒有target。end = mid - 1，
2.2如果nums[mid]==target，在正常的二分查找中，這種情況是可以直接返回結果。但是因為我們是要查找右邊界，這就有可能mid的右邊還有可能有target這個數。因此需要進行兩步操作。
? 2.2.1 用一個變量res標記mid的值，如果左邊還有數值等于target，則更新res的值。否則直接返回res即可。
? 2.2.2 start = mid + 1，繼續向右查找。
2.3 如果nums[mid] < target, 同1.2.2 start = mid + 1，繼續向右查找。
其實說白了，找target，找target的左邊界或者找target的右邊界僅僅是在nums[mid]==target的處理上有差別。

代碼

public?int[]?searchRange(int[]?nums,?int?target)?{
????????assert?nums!=?null;
????????if(nums.length?==?0){
????????????return?new?int[]{-1,-1};
????????}
????????int[]?res?=?new?int[]{findLeft(nums,?target),findRight(nums,?target)};
????????return?res;
????}


????private?int?findLeft(int[]?nums,?int?target){
????????int?len?=?nums.length;
????????int?res?=?-1;
????????int?start?=?0;
????????int?end?=?len?-?1;
????????while?(start?<=?end){
????????????int?mid?=?start?+?(end?-?start)/2;
????????????if(nums[mid]?????????????????start?=?mid?+?1;
????????????}
?????????????else?{
????????????????if(nums[mid]?==?target){
????????????????????res?=?mid;
????????????????}
????????????????end?=?mid?-?1;
????????????}
????????}

????????return?res;

????}

????private?int?findRight(int[]?nums,?int?target){
????????int?len?=?nums.length;
????????int?res?=?-1;
????????int?start?=?0;
????????int?end?=?len?-?1;
????????while?(start?<=?end){
????????????int?mid?=?start?+?(end?-?start)/2;
????????????if(nums[mid]?>?target){
????????????????end?=?mid?-?1;
????????????}
????????????else?{
????????????????if(nums[mid]?==?target){
????????????????????res?=?mid;
????????????????}
????????????????start?=?mid?+?1;

????????????}
????????}

????????return?res;

????}

長按訂閱更多面經分享

總結

以上是生活随笔為你收集整理的去掉数组最后一个元素_leetcode 34. 在排序数组中查找元素的第一个和最后一个位置每天刷一道leetcode算法系列！...的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。