【Leetcode 33】搜索旋转排序数组 —— 二分查找|分治法
2023-12-29 13:03:36
33. 搜索旋转排序数组
整数数组nums
按升序排列,数组中的值互不相同。
在传递给函数之前,nums
在预先未知的某个下标 k(0 <= k < nums.length)上进行了 旋转,使数组变为 [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]](下标 从 0 开始 计数)。
例如, [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。
给你旋转后的数组nums
和一个整数target
,如果nums
中存在这个目标值target
,则返回它的下标,否则返回 -1 。
你必须设计一个时间复杂度为O(log n)
的算法解决此问题。
示例 1:
输入:nums = [4,5,6,7,0,1,2], target = 0
输出:4
题目分析
解决旋转排序数组问题的一种常见方法是使用二分查找
数组被旋转后,可以分为两个有序的子数组。以旋转点为分界,左子数组的所有元素都大于右子数组的所有元素。
- 找到数组的中间元素 mid,如果
nums[left] <= nums[mid]
说明左子数组升序,再判断target
是否在左子数组来决定二分查找左/右子数组;如果右子数组升序同理 - 如果遍历整个数组仍然没有找到目标值,则返回 -1
二分查找算法是用分治策略实现对n个元素进行排序的算法。详细可见 分治法的基本思想与例子解析
其基本思想是:将待排序元素分成大小大致相同的2个子集合,分别对2个子集合进行排序,最终将排好序的子集合合并为所要求的排好序的集合。
class Solution {
public int search(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (target == nums[mid]) {
return mid;
}
if (nums[mid] >= nums[left]) {
if (nums[mid] > target && target >= nums[left]) {
right = mid - 1;
} else {
left = mid + 1;
}
} else {
if (nums[mid] < target && target <= nums[right]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
}
return -1;
}
}
文章来源:https://blog.csdn.net/why_still_confused/article/details/135279751
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!