問題描述
給定一個按照升序排列的整數陣列 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]
解題思路：
1.順序查找法
方式一：順序查找法，按照順序進行查找，當第一次找到了這個元素就可以得到其起始位置，然后從起始位置開始找，如果發現后面的元素剛好不等于目標元素，則前面一個位置就是終點位置，
2.二分查找法
由于陣列已經排序，因此整個陣列是單調遞增的，我們可以利用二分法來加速查找的程序，
二分法的思想是在一個區間內部二分邊界，每次選擇在哪一個區間的時候，選擇目標元素所在的區間進行下一步的處理，每次都能保證我們區間里面一定有答案，當區間長度是1的時候，指標所指的元素就一定是答案，二分的時候一定能求出最終結果，
大雪菜老師給出的二分搜索
bool check(int x) {/* ... */} // 檢查x是否滿足某種性質
// 區間[l, r]被劃分成[l, mid]和[mid + 1, r]時使用：
int bsearch_1(int l, int r)
{
while (l < r)
{
int mid = l + r >> 1;
if (check(mid)) r = mid; // check()判斷mid是否滿足性質
else l = mid + 1;
}
return l;
}
// 區間[l, r]被劃分成[l, mid - 1]和[mid, r]時使用：
/*
當更新區間包含left=mid時，需要補上mid+1，
比如(left+right)/2,如果left=right-1,(left+right)/2=left,那么left=mid時，就會死回圈
*/
int bsearch_2(int l, int r)
{
while (l < r)
{
int mid = l + r + 1 >> 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
return l;
}
首先，這里要明確我們查找的是目標元素的起始位置和最后一個位置，我們可以使用兩個while回圈，第一次查找目標元素的出現的第一個位置，使用一個while回圈，如果nums[mid]>=target,那么我們要查找的區間必定在[left,mid],這里mid也滿足條件，當nums[mid]<target時，那么我們要查找的區間則在[mid+1,right].如果第一次沒有查找到，就說明陣列中不存在目標元素，直接按照要求回傳-1，-1
第二次查找目標元素出現的最后一個位置，注意，這里在計算mid的時候，我們應該加1，原因是因為：nums[mid]<=target，//此時要查找的區間是[mid,right]，令left=mid，繼續查找，nums[mid]>target,此時要查找的區間是[left,mid-1]，而當我們出現left=mid的時候，如果left=right-1,(left+right)/2=left,那么left=mid時，就會死回圈，
public int[] searchRange(int[] nums, int target) {
int result[]=new int[2];
int len=nums.length;
if(len==0){
result[0]=-1;
result[1]=-1;
return result;
}
int left=0,right=len-1;
int mid=(left+right)>>1;
//查找元素的第一個位置
while(left<right){
if(nums[mid]>target){
//此時需要查找的區間是[left,mid-1]
right=mid-1;
}else if(nums[mid]==target){
//此時需要查找的區間是[left,mid]
right=mid;
}else{
//此時需要查找的區間是[mid+1,right]
left=mid+1;
}
mid=(left+right)>>1;;
}
if(nums[left]!=target){
result[0]=-1;
result[1]=-1;
return result;
}
result[0]=left;
System.out.println(left);
left=0;
right=len-1;
mid=(left+right+1)>>1;
//查找元素出現的最后一個位置
/*
當更新區間是left=mid時，需要補上mid+1，
比如(left+right)/2,如果left=right-1,(left+right)/2=left,那么left=mid時，就會死回圈
*/
while(left<right){
if(nums[mid]<target){
//此時要查找的區間是[mid+1,right]
left=mid+1;
}else if(nums[mid]==target){
//此時要查找的區間是[mid,right]
left=mid;
}else{
//此時要查找的區間是[left,mid-1]
right=mid-1;
}
mid=(left+right+1)>>1;
}
result[1]=left;
return result;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/259147.html
標籤：其他
下一篇：Qt如何加載libxl庫