LeetCode -- Search for a Range

LeetCode -- Search for a Range

題目描述：


Given a sorted array of integers, 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].


就是在排序的數組中找到一個區間的起始和終止邊界索引。




思路：
1. 對於目標數target,在數組nums中使用二分查找到該值的一個索引i
2. 找到nums[i] < target的左邊界，i∈[0,i), 找到nums[j] > target的右邊界，j∈[i,n)




實現代碼：

public class Solution {
public int[] SearchRange(int[] nums, int target) 
{
    if(target > nums[nums.Length - 1] || target < nums[0]){
		return new int[2]{-1,-1};
	}
	
   var i = Array.BinarySearch(nums,target);
   if(i < 0){
   		return new int[2]{-1,-1};
   }
   
   var l = i;
   var r = i;
	while(l >= 0 && nums[l] == target){
		l --;
	}
	
	while(r < nums.Length && nums[r] == target){
		r++;
	}
   
   return new int[2]{l+1,r-1};
}
    
    
}