第22天(简单题中等题 二分查找)

打卡第二十二天
1道简单题+3道中等题

题目:

思路:

代码:

class Solution {
public:bool search(vector<int> &nums, int target) {int n = nums.size();if (n == 0) {//数组为空直接返回 falsereturn false;}if (n == 1) {//数组只有一个元素，直接比较是否等于目标值return nums[0] == target;}int l = 0, r = n - 1;//初始化左右指针，开始二分搜索循环while (l <= r) {int mid = l + (r - l) / 2;if (nums[mid] == target) {//如果中点值等于目标值，直接返回 truereturn true;}if (nums[l] == nums[mid] && nums[mid] == nums[r]) {//当左端点、中点、右端点的值都相等时,无法判断哪边有序，只能同时收缩左右边界++l;--r;} else if (nums[l] <= nums[mid]) {//如果左半部分有序（左端点 <= 中点）if (nums[l] <= target && target < nums[mid]) {//如果目标值在有序的左半部分范围内，搜索左半部分r = mid - 1;} else {//搜索右半部分l = mid + 1;}} else {//右半部分有序if (nums[mid] < target && target <= nums[n - 1]) {//如果目标值在有序的右半部分范围内，搜索右半部分l = mid + 1;} else {//搜索左半部分r = mid - 1;}}}return false;//循环结束没找到，返回 false}
};

三值相等时的处理：通过++l; --r; 来跳过无法判断的情况

耗时≈1.5小时 明天继续