当前位置:网站首页>【Hot100】33. 搜索旋转排序数组
【Hot100】33. 搜索旋转排序数组
2022-07-05 12:56:00 【王六六的IT日常】
33. 搜索旋转排序数组
中等题
但凡是从有序序列中找某个数,第一反应 应该是「二分」。
一个原本有序的数组在某个点上进行了旋转,其实就是将原本一段升序的数组分为了两段。
「二分」的本质是两段性,并非单调性。只要一段满足某个性质,另外一段不满足某个性质,就可以用「二分」。
经过旋转的数组,显然前半段满足 >= nums[0],而后半段不满足 >= nums[0]。我们可以以此作为依据,通过「二分」找到旋转点。
class Solution {
public int search(int[] nums, int target) {
//数组长度
int n = nums.length;
//数组中无元素
if (n == 0) {
return -1;
}
//数组中有一个元素
if (n == 1) {
return nums[0] == target ? 0 : -1;
}
//定义二分查找的左右边界
int l = 0, r = n - 1;
while (l <= r) {
int mid = (l + r) / 2;
if (nums[mid] == target) {
return mid;
}
if (nums[0] <= nums[mid]) {
//如果target在[l,mid]内一直缩小右边界
if (nums[0] <= target && target < nums[mid]) {
r = mid - 1;
} else {
// target<nums[0] ,target>nums[mid] 不在[l,mid]区间内,往右找
l = mid + 1;
}
} else {
//nums[0] > nums[mid] [5,6,0,1,2,3,4]
if (nums[mid] < target && target <= nums[n - 1]) {
l = mid + 1;
} else {
r = mid - 1;
}
}
}
return -1;
}
}
边栏推荐
- RHCSA2
- How to protect user privacy without password authentication?
- 关于 SAP UI5 getSAPLogonLanguage is not a function 的错误消息以及 API 版本的讨论
- It's too convenient. You can complete the code release and approval by nailing it!
- Navigation property and entityset usage in SAP segw transaction code
- The Research Report "2022 RPA supplier strength matrix analysis of China's banking industry" was officially launched
- PyCharm安装第三方库图解
- Solve Unicode decodeerror: 'GBK' codec can't decode byte 0xa2 in position 107
- Introduction to sap ui5 dynamicpage control
- Natural language processing series (I) introduction overview
猜你喜欢
精彩速递|腾讯云数据库6月刊
解决 UnicodeDecodeError: ‘gbk‘ codec can‘t decode byte 0xa2 in position 107
Asemi rectifier bridge hd06 parameters, hd06 pictures, hd06 applications
将函数放在模块中
《2022年中國銀行業RPA供應商實力矩陣分析》研究報告正式啟動
Overflow toolbar control in SAP ui5 view
百日完成国产数据库opengausss的开源任务--openGuass极简版3.0.0安装教程
[cloud native] event publishing and subscription in Nacos -- observer mode
Datapipeline was selected into the 2022 digital intelligence atlas and database development report of China Academy of communications and communications
Hundred days to complete the open source task of the domestic database opengauss -- openguass minimalist version 3.0.0 installation tutorial
随机推荐
Simple page request and parsing cases
前缀、中缀、后缀表达式「建议收藏」
RHCSA4
From the perspective of technology and risk control, it is analyzed that wechat Alipay restricts the remote collection of personal collection code
Natural language processing series (I) introduction overview
I'm doing open source in Didi
你的下一台电脑何必是电脑,探索不一样的远程操作
APICloud Studio3 WiFi真机同步和WiFi真机预览使用说明
RHCSA1
Pandora IOT development board learning (HAL Library) - Experiment 7 window watchdog experiment (learning notes)
时钟周期
Discussion on error messages and API versions of SAP ui5 getsaplogonlanguage is not a function
Write macro with word
Talk about my drawing skills in my writing career
国际自动机工程师学会(SAE International)战略投资几何伙伴
leetcode:221. Maximum square [essence of DP state transition]
Datapipeline was selected into the 2022 digital intelligence atlas and database development report of China Academy of communications and communications
Compile kernel modules separately
How to realize batch sending when fishing
手把手带你入门Apache伪静态的配置