当前位置:网站首页>【Hot100】33. Search rotation sort array
【Hot100】33. Search rotation sort array
2022-07-05 13:14:00 【Wang Liuliu's it daily】
33. Search rotation sort array
Medium question
However, it is to find a number from an ordered sequence , First reaction Should be 「 Two points 」.
An originally ordered array rotates at a certain point , In fact, it is to divide the original ascending array into two segments .
「 Two points 」 The essence of is two-stage , Not monotonicity . As long as a paragraph satisfies a certain property , Another paragraph does not satisfy a certain property , You can use it 「 Two points 」.
Rotated array , Obviously, the first half meets >= nums[0], The latter half is not satisfied >= nums[0]. We can use this as a basis , adopt 「 Two points 」 Find the rotation point .
class Solution {
public int search(int[] nums, int target) {
// The length of the array
int n = nums.length;
// There are no elements in the array
if (n == 0) {
return -1;
}
// There is an element in the array
if (n == 1) {
return nums[0] == target ? 0 : -1;
}
// Define the left and right boundaries of binary search
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]) {
// If target stay [l,mid] Inner always reduces the right boundary
if (nums[0] <= target && target < nums[mid]) {
r = mid - 1;
} else {
// target<nums[0] ,target>nums[mid] be not in [l,mid] Within the interval , Look to the right
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;
}
}
边栏推荐
- Principle and performance analysis of lepton lossless compression
- Go pointer
- SAP UI5 DynamicPage 控件介紹
- 山东大学暑期实训一20220620
- Talking about fake demand from takeout order
- SAP ui5 objectpagelayout control usage sharing
- 同事半个月都没搞懂selenium,我半个小时就给他整明白!顺手秀了一波爬淘宝的操作[通俗易懂]
- Talk about seven ways to realize asynchronous programming
- Natural language processing series (I) introduction overview
- 实现 1~number 之间,所有数字的加和
猜你喜欢
Didi open source Delta: AI developers can easily train natural language models
量价虽降,商业银行结构性存款为何受上市公司所偏爱?
Asemi rectifier bridge hd06 parameters, hd06 pictures, hd06 applications
函数传递参数小案例
Go array and slice
Simple page request and parsing cases
MySQL giant pit: update updates should be judged with caution by affecting the number of rows!!!
SAP SEGW 事物码里的导航属性(Navigation Property) 和 EntitySet 使用方法
A detailed explanation of ASCII code, Unicode and UTF-8
Overflow toolbar control in SAP ui5 view
随机推荐
PyCharm安装第三方库图解
事务的基本特性和隔离级别
Concurrent performance test of SAP Spartacus with JMeter
STM32 and motor development (from architecture diagram to documentation)
“百度杯”CTF比赛 九月场,Web:Upload
946. 验证栈序列
go 指针
Introduction to the principle of DNS
【Hot100】33. 搜索旋转排序数组
MATLAB论文图表标准格式输出(干货)
函数的默认参数&函数参数的多种方法
How to choose note taking software? Comparison and evaluation of notion, flowus and WOLAI
leetcode:221. 最大正方形【dp状态转移的精髓】
Pandora IOT development board learning (HAL Library) - Experiment 7 window watchdog experiment (learning notes)
前缀、中缀、后缀表达式「建议收藏」
SAP UI5 DynamicPage 控件介绍
Lb10s-asemi rectifier bridge lb10s
Cf:a. the third three number problem
OpenHarmony应用开发之Navigation组件详解
#从源头解决# 自定义头文件在VS上出现“无法打开源文件“XX.h“的问题