Description
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].
Code
class Solution(object):
def searchRange(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
if not nums:
return [-
1, -
1]
l =
0
r = len(nums) -
1
mid = (l + r) /
2
res = [-
1, -
1]
while l <= r:
if nums[mid] < target:
l = mid +
1
mid = (l + r) /
2
elif nums[mid] > target:
r = mid -
1
mid = (l + r) /
2
else:
return [self.findStart(mid, nums), self.findEnd(mid, nums)]
return res
def findStart(self, mid, nums):
l =
0
m = (l + mid) /
2
while l < mid:
if nums[m] == nums[mid]:
if nums[m -
1] < nums[mid]:
return m
else:
mid = m
m = (l + mid) /
2
if mid == m:
m -=
1
if nums[m] < nums[mid]:
if nums[m +
1] == nums[mid]:
return m +
1
else:
l = m +
1
m = (l + mid) /
2
return 0
def findEnd(self, mid, nums):
r = len(nums) -
1
m = (mid + r) /
2
while r > mid:
if nums[m] == nums[mid]:
if nums[m +
1] > nums[mid]:
return m
else:
mid = m
m = (mid + r) /
2
if mid == m:
if m +
1 >= len(nums) -
1:
return m +
1
if nums[m] > nums[mid]:
if nums[ m -
1] == nums[mid]:
return m -
1
else:
r = m -
1
m = (r + mid) /
2
return len(nums) -
1
这题也是个二分查找的变形，因为题目要求了时间复杂度，所以全程用的是二分法，然后在二分法的基础上进行变形，满足题目要求。虽然代码通过了，用时也是中等，但我觉得这代码真是太屎了，没办法，想不到好的算法，先最简单的方法实现了再说。
Code2(author:stellari)
vector<int> searchRange(
int A[],
int n,
int target) {
int i =
0, j = n -
1;
vector<int> ret(
2, -
1);
while (i < j)
{
int mid = (i + j) /
2;
if (A[mid] < target) i = mid +
1;
else j = mid;
}
if (A[i]!=target)
return ret;
else ret[
0] = i;
j = n-
1;
while (i < j)
{
int mid = (i + j) /
2 +
1;
if (A[mid] > target) j = mid -
1;
else i = mid;
}
ret[
1] = j;
return ret;
}
Conclusion
看了看别人的代码，总的来说都是变异的二分法，不过别人写的的确是简洁，是得学习学习。
