原题目：Search for a Range， 现在题目改为： 34. Find First and Last Position of Element in Sorted Array
Given an array of integers nums 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].
Example 1:
Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]
Example 2:
Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]
给一个有序整数数组中，寻找相同目标值的起始和结束位置，限定了时间复杂度为O(logn)。
解法：二分法，典型的二分查找法的时间复杂度，先对原数组使用二分查找法，找出其中一个目标值的位置，然后向两边搜索找出起始和结束的位置。
Java:
public class Solution {
public int[] searchRange(int[] A, int target) {
int start = Solution.firstGreaterEqual(A, target);
if (start == A.length || A[start] != target) {
return new int[]{-1, -1};
}
return new int[]{start, Solution.firstGreaterEqual(A, target + 1) - 1};
}
//find the first number that is greater than or equal to target.
//could return A.length if target is greater than A[A.length-1].
//actually this is the same as lower_bound in C++ STL.
private static int firstGreaterEqual(int[] A, int target) {
int low = 0, high = A.length;
while (low < high) {
int mid = low + ((high - low) >> 1);
//low <= mid < high
if (A[mid] < target) {
low = mid + 1;
} else {
//should not be mid-1 when A[mid]==target.
//could be mid even if A[mid]>target because mid<high.
high = mid;
}
}
return low;
}
}
Python:
class Solution(object):
def searchRange(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
# Find the first idx where nums[idx] >= target
left = self.binarySearch(lambda x, y: x >= y, nums, target)
if left >= len(nums) or nums[left] != target:
return [-1, -1]
# Find the first idx where nums[idx] > target
right = self.binarySearch(lambda x, y: x > y, nums, target)
return [left, right - 1] def binarySearch(self, compare, nums, target):
left, right = 0, len(nums)
while left < right:
mid = left + (right - left) / 2
if compare(nums[mid], target):
right = mid
else:
left = mid + 1
return left def binarySearch2(self, compare, nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = left + (right - left) / 2
if compare(nums[mid], target):
right = mid - 1
else:
left = mid + 1
return left def binarySearch3(self, compare, nums, target):
left, right = -1, len(nums)
while left + 1 < right:
mid = left + (right - left) / 2
if compare(nums[mid], target):
right = mid
else:
left = mid
return left if left != -1 and compare(nums[left], target) else right
C++:
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
const auto start = lower_bound(nums.cbegin(), nums.cend(), target);
const auto end = upper_bound(nums.cbegin(), nums.cend(), target);
if (start != nums.cend() && *start == target) {
return {start - nums.cbegin(), end - nums.cbegin() - 1};
}
return {-1, -1};
}
};
class Solution2 {
public:
vector<int> searchRange(vector<int> &nums, int target) {
const int begin = lower_bound(nums, target);
const int end = upper_bound(nums, target);
if (begin < nums.size() && nums[begin] == target) {
return {begin, end - 1};
}
return {-1, -1};
}
private:
int lower_bound(vector<int> &nums, int target) {
int left = 0;
int right = nums.size();
// Find min left s.t. A[left] >= target.
while (left < right) {
const auto mid = left + (right - left) / 2;
if (nums[mid] >= target) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
int upper_bound(vector<int> &nums, int target) {
int left = 0;
int right = nums.size();
// Find min left s.t. A[left] > target.
while (left < right) {
const auto mid = left + (right - left) / 2;
if (nums[mid] > target) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
};