给出一个有序数组,请在数组中找出目标值的起始位置和结束位置
你的算法的时间复杂度应该在O(log n)之内
如果数组中不存在目标,返回[-1, -1].
例如:
给出的数组是[50, 70, 70, 80, 80, 100],目标值是80,
返回[3, 4].
class Solution { public: vector<int> searchRange(int A[], int n, int target) { /// 方法1: 使用STL中的lower_bound,upper_bound或者equal_bound解决 /* vector<int> res(2,-1); if(A==nullptr || n <=0) return res; int low = lower_bound(A,A+n,target)-A; if(low==n || A[low]!=target) return res; else res[0] = low; int high = upper_bound(A,A+n,target)-A-1; res[1] = high; return res; */ /// 方法2:使用二分查找,查找左右边界即可 vector<int> res(2,-1); if(A==nullptr || n<=0) return res; int low = 0,high = n-1; while(low<=high) { int middle = (high+low)>>1; if(A[middle] < target) /// 向左夹逼,则找到左边界 low = middle+1; else high = middle-1; } int low2 = 0,high2 = n-1; while(low2 <=high2) { int middle2 = (high2+low2)>>1; if(A[middle2] <= target) /// 向右夹逼,找到右边界 low2 = middle2+1; else high2 = middle2-1; } if(low <= high2) { res[0] = low; res[1] = high2; } return res; } };
public class Solution { public int[] searchRange(int[] A, int target) { int low = 0, high = A.length - 1, mid = 0; int start = - 1, end = - 1; while (low <= high) { mid = (low + high) / 2; if(A[mid] < target) low = mid + 1; else if(A[mid] > target) high = mid - 1; else { start = end = mid; while (start >= 0 && A[start] == target) start --; while (end < A.length && A[end] == target) end ++; return new int[] {start + 1, end - 1}; } } return new int[] {start, end}; } }
详细过程见我CSDN博客:https://blog.csdn.net/weixin_42047723/article/details/93721826
我们先来看看时间复杂度为O(n)的算法,分别从左遍历和从右遍历数组,找到目标数的第一个下标位置分为是要求解的目标值的起始和结束位置
public class Solution { public int[] searchRange(int[] A, int target) { int res[] = new int[2]; res[0] = -1; res[1] = -1; //向左找 for(int i = 0 ; i < A.length; i++){ if(A[i] == target){ res[0] = i; break; } } //向右找 for(int i = A.length - 1 ; i >= 0; i--){ if(A[i] == target){ res[1] = i; break; } } return res; } }
若要求时间复杂度为O(log n),我们可以利用二分查找的方法,该算法的时间复杂度为O(log n)。通过两次二分法查找,找到目标值的左边界和右边界,需要对二分查找法稍微加以修改。当查找右边界时,即当A[middle]小于等于目标数target时,low游标自增1继续往右走。同理当查找左边界时,即当A[middle]大于等于目标数target时,high游标自减1继续往左走。
public class Solution { public int[] searchRange(int[] A, int target) { int len = A.length; int res[] = new int[2]; res[0] = -1; res[1] = -1; int low1 = 0, high1 = len - 1; //查找右边界 while(low1 <= high1){ int middle1 = (low1 + high1) / 2; if(A[middle1] <= target) low1 = middle1 + 1; else high1 = middle1 - 1; } int low2 = 0, high2 = len - 1; //查找左边界 while(low2 <= high2){ int middle2 = (low2 + high2) / 2; if(A[middle2] >= target) high2 = middle2 - 1; else low2 = middle2 + 1; } if(low2 <= high1){ res[0] = low2; res[1] = high1; } return res; } }
class Solution { public: vector<int> searchRange(int A[], int n, int target) { int l=0,r=n-1,l2=0,r2=n-1; while(l<=r){ int mid=l+(r-l)/2; if(A[mid]<target) l=mid+1; else r=mid-1; } while(l2<=r2){ int mid=l2+(r2-l2)/2; if(A[mid]>target) r2=mid-1; else l2=mid+1; } vector<int> vec(2,-1); if(l<=r2) vec[0]=l,vec[1]=r2; return vec; } };
class Solution { public: vector<int> searchRange(int A[], int n, int target) { //时间复杂度为O(logn) int l=0,h=n,m; int start=-1,end=-1; while(l<h){ m = l+((h-l)>>1); if(A[m]>target){ h=m; }else if(A[m]<target){ l=m+1; }else{//找到以后,需要确定前后边界 int index = m; while(index>=0&&A[index]==target)index--; start = index+1; index=m; while(index<n&&A[index]==target)index++; end = index-1; break; } } vector<int> res; res.push_back(start); res.push_back(end); return res; } };
class Solution { public: /** * * @param A int整型一维数组 * @param n int A数组长度 * @param target int整型 * @return int整型vector */ vector<int> searchRange(int* A, int n, int target) { // write code here if (n<1) return vector<int>{-1,-1}; if (n==1){ if (A[0]==target) return vector<int>{0,0}; else return vector<int>{-1,-1}; } vector<int> ans; int l=0,r=n-1; while (l<r){ //第一次二分找到第一个等于目标值 int mid=(l+r)>>1; if (A[mid]>target) r=mid-1; else if (A[mid]<target) l=mid+1; else r=mid; } if (A[r]!=target) return vector<int>{-1,-1}; ans.push_back(r); l=r,r=n-1; while (l<r){//第二次二分找到最后一个等于目标值的 int mid=(l+r+1)>>1;//此处加1的目的,让除法向上取整 if (A[mid]>target) r=mid-1; else if (A[mid]<target) l=mid+1; else l=mid; } ans.push_back(l); return ans; } };
class Solution { public: vector<int> searchRange(int A[], int n, int target) { int l = 0; int r = n-1; vector<int> res; while(l <= r) { int mid = l + (r-l)/2; if(A[mid] == target) { if(A[l] == target && A[r] == target) { res.push_back(l); res.push_back(r); return res; } if(A[l] != target) ++l; if(A[r] != target) --r; } else if(A[mid] < target) l = mid + 1; else r = mid-1; } return vector<int>(2,-1); } };
class Solution { public: vector<int> searchRange(int A[], int n, int target) { // 返回起始位置 有序数组 vector<int> res(2,-1); int left = 0; int right = n - 1; int flag = 0; int mid; while(left <= right) { mid = (right - left)/2 + left; if(A[mid] == target) { flag = 1; break; } else if(A[mid] < target) left = mid + 1; else right = mid - 1; } if( flag != 0) { int i = 1 , j = 1; while(mid - i >= 0 && A[mid - i] == target) i++; while(mid + j < n && A[mid + j] == target) j++; res[0] = (mid - i + 1); res[1] = (mid + j - 1); } return res; } };
class Solution { public: // 一种新的思路,供大家参考 // 改进二分查找,并通过修改target的值,使得最多经两次二分查找即可获得元素所在的区间 // 复杂度O(logn) ~ O(2logn), 处于O(logn)级别,符合题目要求 // 该算法最后的if-else判断应该还可以改进,如有好的想法请回复 vector<int> searchRange(vector<int>& nums, int target) { if (nums.empty()) return {-1, -1}; int min_rank = -1, max_rank = -1; int lo = 0, hi = nums.size(); while (lo < hi) { // 改进二分查找,使其总能返回多个命中元素的秩最大者。耗时O(logn) int mi = lo + ((hi - lo) >> 1); (target < nums[mi]) ? hi = mi : lo = mi + 1; } // 循环结束时,lo为大于target的元素的最小秩,故 --lo 即不大于target的元素的最大秩 if (--lo != -1 && nums[lo] == target) { // 如target不存在可提前退出 max_rank = lo; // 此时的lo即为target的最大秩(如存在) --target; hi = lo; lo = 0; // 第二次二分查找查找对象变为target - 1,查找区间缩小至[0, max_rank) while (lo < hi) { // 耗时O(log(max_rank + 1)) int mi = lo + ((hi - lo) >> 1); (target < nums[mi]) ? hi = mi : lo = mi + 1; } // 循环结束时,lo为大于 target - 1 的元素的最小秩,即target的最小秩(如存在) min_rank = lo; // 此时的lo即为target的最小秩(如存在) } if (min_rank == -1) return {-1, -1}; else return {min_rank, max_rank}; } };
//二分法分别查找左右端点
public class Solution {
public int[] searchRange(int[] A, int target) {
int [] range = new int[2];
range[0]= searchleft(A, target);
range[1]= searchright(A, target);
return range;
}
public int searchleft(int[] A, int target) {
int low=0;
int high= A.length-1;
while (low<=high) {
int mid=(low+high)>>1;
if (target==A[mid]) {
if (mid==0||A[mid-1]<target) {
return mid;
}
high=mid-1;
}else if (target<A[mid]) {
high=mid-1;
}else {
low=mid+1;
}
}
return -1;
}
public int searchright(int[] A, int target) {
int low=0;
int high= A.length-1;
while (low<=high) {
int mid=(low+high)>>1;
if (target==A[mid]) {
if (mid==A.length-1||A[mid+1]>target) {
return mid;
}
low=mid+1;
}else if (target<A[mid]) {
high=mid-1;
}else {
low=mid+1;
}
}
return -1;
}
}
public class Solution {
public int[] searchRange(int[] A, int target) {
int lo=0,hi=A.length-1;
int left=-1,right=-1;
while(lo<=hi){
int mid=(hi-lo)/2+lo;
if(target<A[mid]){
hi=mid-1;
}else if(target>A[mid]){
lo=mid+1;
}else{
left=mid;
right=mid;
if(A[left]==target&&left-1>=lo&&A[left-1]==target){
int lo1=lo,hi1=mid-1;
while(lo1<=hi1){
int leftmid=(hi1-lo1)/2+lo1;
if(A[leftmid]<target){
lo1=leftmid+1;
}else if(A[leftmid]>target){
hi1=leftmid-1;
}else{
if(leftmid-1>=lo&&A[leftmid-1]==target){
hi1=leftmid-1;
}else{
left=leftmid;
break;
}
}
}
}
if(A[right]==target&&right+1<=hi&&A[right+1]==target){
int lo2=mid+1,hi2=hi;
while(lo2<=hi2){
int rightmid=(hi2-lo2)/2+lo2;
if(A[rightmid]<target){
lo2=rightmid+1;
}else if(A[rightmid]>target){
hi2=rightmid-1;
}else{
if(rightmid+1<=hi&&A[rightmid+1]==target){
lo2=rightmid+1;
}else{
right=rightmid;
break;
}
}
}
}
break;
}
}
int[] result={left,right};
return result;
}
}
/*
Given an array of integers sorted in ascending order, find the starting and ending position of a given target value.
Your algorithm's runtime complexity must be in the order of O(log n).
If the target is not found in the array, return [-1, -1].
For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].
*/
/*
思路:
使用二分查找法,
先找到一个target,然后分别向左和向右搜索target的边缘
*/
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
int n = nums.size();
vector<int> v;
v.push_back(-1);
v.push_back(-1);
int left = 0, right = n - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
theRes(nums, v, mid, target);
return v;
}
else if (nums[mid] < target) {
left = mid + 1;
}
else {
right = mid - 1;
}
}
return v;
}
void theRes(vector<int>& nums, vector<int>& v, int index, int target) {
// 向左遍历
int left = index;
for (int i = index - 1; i >= 0; --i) {
if (nums[i] == target) {
left = i;
}
else {
break;
}
}
v[0] = left;
int right = index;
for (int i = index + 1; i < nums.size(); ++i) {
if (nums[i] == target) {
right = i;
}
else {
break;
}
}
v[1] = right;
}
};
vector<int> searchRange(int A[], int n, int target) { vector<int> res; int low=0; int high=n-1; int mid; while(low<=high){ mid=(low+high)/2; if(A[mid]==target){ int i=mid; while(i-1>=0&&A[i]==A[i-1]) i--; int j=mid; while(j+1<=high&&A[j]==A[j+1]) j++; res.push_back(i); res.push_back(j); return res; } else if(A[mid]<target) low=mid+1; else high=mid-1; } res.push_back(-1); res.push_back(-1); return res; }
class Solution { public: vector<int> searchRange(int A[], int n, int target) { int l1=0,r1=n-1,l2=0,r2=n-1; while(l1 <= r1) { int mid = l1+((r1-l1)>>1); if(A[mid] < target) l1 = mid + 1; else r1 = mid - 1; } while(l2 <= r2) { int mid = l2+((r2-l2)>>1); if(A[mid] > target) r2 = mid - 1; else l2 = mid + 1; } vector<int> result(2,-1); if(l1 <= r2) { result[0] = l1; result[1] = r2; } return result; } };
public class Solution { public int[] searchRange(int[] A, int target) { int[] a = {-1,-1}; if(A==null||a.length<2) return a; int low, high, mid; low = 0; high = A.length - 1; while (low <= high) { mid = (high + low) / 2; if (target == A[mid]) { int temp = mid; //向前搜索 while (mid - 1 >=0 && A[mid - 1] == target) { mid--; } a[0] = mid; mid = temp; //向后搜索 while (mid + 1 < A.length && A[mid + 1] == target) { mid++; } a[1] = mid; break; } else if (target < A[mid]) { high = mid - 1; } else { low = mid + 1; } } return a; } }
import java.util.*; public class Solution { /** * * @param A int整型一维数组 * @param target int整型 * @return int整型一维数组 */ public int[] searchRange (int[] A, int target) { // write code here if(A[0] > target || A[A.length-1] < target){ return new int[]{-1, -1}; } int index = process(A, 0, A.length-1, target); if(index == -1){ return new int[]{-1,-1}; } return getRange(A, index); } private static int process(int[] arr, int l, int r, int target){ if(l == r){ return arr[l] == target ? l : -1; } int index = l+(r-l)/2; if(arr[index] == target){ return index; } if(arr[index] > target){ return process(arr, l, index-1, target); }else{ return process(arr, index+1, r, target); } } private static int[] getRange(int[] arr, int index){ int l = index; int r = index; while(l > 0 && arr[l-1] == arr[index]){ l--; } while(r < arr.length-1 && arr[r+1] == arr[index]){ r++; } return new int[]{l, r}; } }