题目
搜索区间
给定一个包含 n 个整数的排序数组，找出给定目标值 target 的起始和结束位置。
如果目标值不在数组中，则返回[-1, -1]
样例
给出[5, 7, 7, 8, 8, 10]和目标值target=8,
返回[3, 4]
挑战
时间复杂度 O(log n)
解题
正常解法是二分法分别找左右边界的，时间复杂度O(logN),但是要注意边界，边界很多种情况的。
找左边界：
1.起始位置是0的单独考虑：nums[0] == target return 0
2.正常的二分查找思想
while(left <= right){
int median = (left + right)/2;
if(nums[median] < target){
left = median+1;
}else if(nums[median]>target){
right = median -1;
}else if(nums[median]==target){
if(nums[median-1]!=target)
return median;
else
right = median - 1;
}
}找右边界：
1.结束位置单独考虑：nums[right] == target return right
2.正常的二分查找思想
while(left <= right){
int median = (left + right)/2;
if(nums[median] < target){
left = median+1;
}else if(nums[median]>target){
right = median -1;
}else if(nums[median]==target){
if(nums[median+1]!=target)
return median;
else
left = median + 1;
}
}Java
public class Solution {
/**
*@param A : an integer sorted array
*@param target : an integer to be inserted
*return : a list of length 2, [index1, index2]
*/
public int[] searchRange(int[] A, int target) {
// write your code here
int[] res = {-1,-1};
int len = A.length;
if(len == 0 || A == null)
return res;
res[0] = BinaryLeft(A,0,len-1,target);
res[1] = BinaryRight(A,0,len-1,target);
return res;
}
public int BinaryLeft(int[] nums,int left,int right,int target){
if(nums[0] == target)
return 0;
while(left <= right){
int median = (left + right)/2;
if(nums[median] < target){
left = median+1;
}else if(nums[median]>target){
right = median -1;
}else if(nums[median]==target){
if(nums[median-1]!=target)
return median;
else
right = median - 1;
}
}
return -1;
}
public int BinaryRight(int[] nums,int left,int right,int target){
if(nums[right] == target)
return right;
while(left <= right){
int median = (left + right)/2;
if(nums[median] < target){
left = median+1;
}else if(nums[median]>target){
right = median -1;
}else if(nums[median]==target){
if(nums[median+1]!=target)
return median;
else
left = median + 1;
}
}
return -1;
}
}Java Code
Python
class Solution:
"""
@param A : a list of integers
@param target : an integer to be searched
@return : a list of length 2, [index1, index2]
"""
def searchRange(self, A, target):
# write your code here
res = [-1,-1]
if A==None or len(A) == 0:
return res
res[0] = self.BoundaryLeft(A,0,len(A)-1,target)
res[1] = self.BoundaryRight(A,0,len(A)-1,target)
return res
def BoundaryLeft(self,A,left,right,target):
if A[0] == target:
return 0
while left<= right:
median = (left + right)/2
if A[median] < target:
left = median + 1
elif A[median] > target:
right = median -1
elif A[median] == target:
if A[median-1]!=target:
return median
else:
right = median -1
return -1 def BoundaryRight(self,A,left,right,target):
if A[right] == target:
return right
while left<= right:
median = (left+ right)/2
if A[median] < target:
left = median + 1
elif A[median] > target:
right = median - 1
elif A[median] == target:
if A[median + 1]!=target:
return median
else:
left = median + 1
return -1
Python Code