33.搜索旋转排序数组

/*
 * @lc app=leetcode.cn id=33 lang=typescript
 *
 * [33] 搜索旋转排序数组
 * 默认数组为升序
 */

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

// console.log(search([4, 5, 6, 7, 0, 1, 2], 0));
console.log(search([1, 3], 1));
// @lc code=end