class Solution {
public:
/**
* @param nums: The integer array.
* @param target: Target to find.
* @return: The first position of target. Position starts from 0.
*/
int binarySearch(vector<int> &nums, int target) {
// write your code here
if(nums.size() == 0) return -1;
int left = 0;
int right = nums.size() - 1;
while(left <= right){
int mid = (left + right) / 2;
cout<<mid<<endl;
if(nums[mid] == target){
int index = mid;
while(index-1 >= 0 && nums[index-1] == target){
index--;
};
return index;
}
if(nums[mid] < target) left = mid+1;
else right = mid - 1;
}
return -1;
}
};
模板好!
public:
/**
* @param A: an integer sorted array
* @param target: an integer to be inserted
* @return: a list of length 2, [index1, index2]
*/
vector<int> searchRange(vector<int> &A, int target) {
// write your code here
vector<int> result;
if(A.empty()) return vector<int> {-1, -1};
int lb = -1;
int ub = A.size();
while(lb + 1 < ub){
int mid = lb + (ub - lb) / 2;
if(target > A[mid]) lb = mid;
else ub = mid;
}
if(A[lb + 1] != target) return vector<int> {-1,-1};
result.push_back(lb + 1) ;
lb = -1, ub = A.size();
while(lb + 1 < ub){
int mid = lb + (ub - lb)/2;
if(target < A[mid]) ub = mid;
else lb = mid;
}
result.push_back(ub - 1) ;
return result;
}
};