34. 在排序数组中查找元素的第一个和最后一个位置
自己做
解：二分查找
class Solution {
public://二分查找int halfFind(vector<int> nums, int begin, int end, int target){if(begin > end) //找不到的情况return -1;int mid = (begin + end) / 2;if(nums[mid] == target) //找到的情况return mid;if(nums[mid] > target) //中轴偏大，往左边继续找return halfFind(nums, begin, mid - 1, target);if(nums[mid] < target) //中轴偏小，往右边继续找return halfFind(nums, mid + 1, end, target);return 0; //应付LeetCode}vector<int> searchRange(vector<int>& nums, int target) {//二分查找到元素int len = nums.size();if(len == 0) //数组为空return {-1,-1}; int k = halfFind(nums, 0, len - 1, target);if(k == -1) //元素不存在return {-1,-1};//元素存在的情况int begin = k, end = k;//先往左边找while(begin >= 0 && nums[begin] == target)begin--;//再往右边找while(end < len && nums[end] == target)end++;return {begin + 1,end - 1};}
};
35. 搜索插入位置
自己做
解：二分查找
class Solution {
public://二分查找int halfFind(vector<int> nums, int begin, int end, int target){if(begin > end) //找不到的情况return end + 1; //返回要插入的下标int mid = (begin + end) / 2;if(nums[mid] == target) //找到的情况return mid;if(nums[mid] > target) //中轴偏大，往左边继续找return halfFind(nums, begin, mid - 1, target);if(nums[mid] < target) //中轴偏小，往右边继续找return halfFind(nums, mid + 1, end, target);return 0; //应付LeetCode}int searchInsert(vector<int>& nums, int target) {int len = nums.size();return halfFind(nums, 0, len - 1, target);}
};
