LeetCode 第34題：在排序數組中查找元素的第一個和最后一個位置

題目描述

給你一個按照非遞減順序排列的整數數組nums，和一個目標值target。請你找出給定目標值在數組中的開始位置和結束位置。如果數組中不存在目標值target，返回[-1,1]。你必須設計并實現時間復雜度為為O（log n）的算法解決此問題。

難度：中等

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

示例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<=105
• -109<=nums[i]<=109
• nums是一個非遞減數組
• -109<=target<=109

解題思路：二分查找

關鍵點：

• 尋找左邊界時，即使找到目標值也繼續向左搜索
• 尋找右邊界時，即使找到目標值也繼續向右搜索
• 兩次二分查找的條件稍有不同?

int binarySearch(int* nums,int numsSize,int target,bool lower)
{int left = 0,right = numsSize-1,ans = numsSize;while(left<=right){int mid=(left+right)/2;if(nums[mid]>target || (lower && nums[mid] >=target)){right = mid-1;ans=mid;}elseleft=mid+1;}return ans;
}int* searchRange(int* nums,int numsSize,int target,int* returnSize)
{int leftIdx = binarySearch(nums,numsSize,target,true);int rightIdx = binarySearch(nums,numsSize,target,false)-1;int* ret = malloc(sizeof(int)*2);*returnSize=2;if(leftIdx<=rightIdx && rightIdx<numsSize && nums[leftIdx]==target && nums[rightIdx]==target){ret[0]=leftIdx,ret[1]=rightIdx;return ret;}ret[0]=-1,ret[1]=-1;return ret;
}

返回的left永遠是首個大于等于target的數的位置,right永遠是首個小于target的數的位置，左邊界按正常查找，右邊查target+0.5即可。5

int binSearch(vector<int>& nums,double target)
{int n=nums.size();int left = 0,right = n-1;while(left<=right){int mid = (left+right)/2;if(nums[mid]>=target) right = mid-1;else left = mid+1;}return left;
}
public:
vector<int> searchRange(vector<int>& nums,int target)
{if(nums.size()==0) return {-1，-1}；int l = binSearch(nums,target);int r=binSearch(nums,target+0.5)-1;if(l>=nums.size() || r<0 || l>r)  return {-1,-1};return {l,r};}

LeetCode 第35題：搜索插入位置

題目描述

給定一個排序數組和一個目標值，在數組中找到目標值，并返回其索引。如果目標值不存在于數組中，返回它將會被按順序插入的位置。請必須使用時間復雜度為O（log n）的算法。

難度：簡單

題目鏈接：35. 搜索插入位置 - 力扣（LeetCode）

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

示例4：

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

提示：

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

解題思路：二分查找

• 初始化左右指針
• 進行二分查找
• 如果找到目標值，直接返回
• 如果找不到，返回left指針位置

int searchInsert(int* nums, int numsSize, int target)
{int left = 0,right = numsSize-1;while(left<=right){int mid = left+(right-left)/2;if(nums[mid] == target)  return mid;else if(nums[mid]<target)  left = mid +1;else  right = mid-1;}return left;
}