33 搜索旋转排序数组

题目链接

难度：中等

思路分析：

二分查找

想

一

想

再

看

答

案

想

一

想

再

看

答

案

代码：

二分查找:

/**
 * @description
 * TODO: 利用二分查找方式
 * 1.利用将数组从中间分开
 * 此时肯定存在前半部分或是后半部分是有序的（重要）
 * 2.对有序部分执行二分查找
 * 3.如果目标值不可能存在于有序部分
 * 4.则将目标查找数组选择在无序部分
 * 5.继续进行1进行判断
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function(nums, target) {
	if (!nums || nums.length === 0) return -1
	let start = 0
	let end = nums.length - 1
	let mid
	while (start <= end) {
		mid = Math.ceil((start + end) / 2)
		// 首尾中全部验证
		if (nums[mid] === target) return mid
		if (nums[start] === target) return start
		if (nums[end] === target) return end
		// 说明前半部分有序
		if (nums[start] < nums[mid]) {
			// 说明目标值存在于有序部分，将末尾设置为mid
			// 判断目标值是否在前半部分
			// 更新索引 继续执行二分查找
			if (nums[start] < target && target < nums[mid]) {
				end = mid - 1
			} else {
				// 说明目标值存在于后半段
				start = mid + 1
			}
		} else {
			// 说明后半部分有序
			// 判断目标值是否在后半部分
			// 更新索引 继续执行二分查找
			if (nums[mid] < target && target < nums[end]) {
				start = mid + 1
			} else {
				end = mid - 1
			}
		}
	}
	return -1
}

鼓励我一下：

觉得还不错的话，给我的项目点个star吧

点个Star支持我一下~