博文中会简要介绍Leetcode P0034题目分析及解题思路。
“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].
基本思路就是二分查找。若找到了则判断找到的这个是否在当前最左边的target的左边，若是则继续往左寻找，反之右边亦然。
以下是Java的题解代码实现。
class Solution {
public int[] searchRange(int[] nums, int target) {
if (nums == null || nums.length == 0)
return this.pos;
if (nums[0] > target || nums[nums.length-1] < target)
return this.pos;
this.binarySearch(nums, 0, nums.length-1, target);
return this.pos;
}
private int[] pos = new int[] {-1, -1};
private void binarySearch(int[] nums, int left, int right, int target) {
if (left > right)
return;
int mid = (left+right)/2;
if (nums[mid] > target)
this.binarySearch(nums, left, mid-1, target);
else if (nums[mid] < target)
this.binarySearch(nums, mid+1, right, target);
else {
if (pos[0] == -1 || pos[0] > mid) {
pos[0] = mid;
this.binarySearch(nums, left, mid-1, target);
}
if (pos[1] == -1 || pos[1] < mid) {
pos[1] = mid;
this.binarySearch(nums, mid+1, right, target);
}
}
}
}
以下是C++的题解代码实现。
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
if (nums.size() == 0)
return this->pos;
if (nums[0] > target || nums[nums.size()-1] < target)
return this->pos;
this->BinarySearch(nums, 0, nums.size()-1, target);
return this->pos;
}
private:
vector<int> pos = {-1, -1};
void BinarySearch(vector<int>& nums, int left, int right, int target) {
if (left > right)
return;
int mid = (left+right)/2;
if (nums[mid] > target)
this->BinarySearch(nums, left, mid-1, target);
else if (nums[mid] < target)
this->BinarySearch(nums, mid+1, right, target);
else {
if (pos[0] == -1 || pos[0] > mid) {
pos[0] = mid;
this->BinarySearch(nums, left, mid-1, target);
}
if (pos[1] == -1 || pos[1] < mid) {
pos[1] = mid;
this->BinarySearch(nums, mid+1, right, target);
}
}
}
};