LeetCode题解34: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].
题解
肯定是二分，但是怎么查是个问题。一种是二分查到一个然后往两边看。这种比较低级。当然我想到的就是这种。还有另一种：一共两次二分查找，一次查最左边的，一次查最右边的。
Java代码如下：
public int[] searchRange(int[] nums, int target) {
int[] result = {-1, -1};
if ( null == nums || 0 == nums.length )
return result;
int left_low = 0;
int left_high = nums.length - 1;
while ( left_low <= left_high ) {
int left_middle = (left_low + left_high) / 2;
if ( nums[left_middle] < target )
left_low = left_middle + 1;
else
left_high = left_middle - 1;
}
int right_low = 0;
int right_high = nums.length - 1;
while ( right_low <= right_high ) {
int right_middle = (right_low + right_high) / 2;
if ( nums[right_middle] <= target )
right_low = right_middle + 1;
else
right_high = right_middle - 1;
}
if ( left_low <= right_high ) {
result[0] = left_low;
result[1] = right_high;
}
return result;
}
Written on January 15, 2016