81.搜索旋转排序数组-ii

/*
 * @lc app=leetcode.cn id=81 lang=typescript
 *
 * [81] 搜索旋转排序数组 II
 * 备注：翻转前nums升序，且元素可能重复
 */

// @lc code=start
function search(nums: number[], target: number): boolean {
	let l = 0,
		r = nums.length - 1;
	while (l <= r) {
		let mid = Math.floor((l + r) / 2);
		if (target == nums[mid]) {
			return true;
		}

		if (nums[l] === nums[mid] && nums[r] == nums[mid]) {
			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 && nums[r] >= target) {
				l = mid + 1;
			} else {
				r = mid - 1;
			}
		}
	}

	return false;
}

console.log(search([2, 5, 6, 0, 0, 1, 2], 2));

// @lc code=end