[LeetCode]33. 搜索旋转排序数组(二分)
2024-10-09 16:32:14
题目
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如,数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
搜索一个给定的目标值,如果数组中存在这个目标值,则返回它的索引,否则返回 -1 。
你可以假设数组中不存在重复的元素。
你的算法时间复杂度必须是 O(log n) 级别
题解
- 由最原始的二分框架来做。
- 如果中间的数小于最右边的数,则右半段是有序的,若中间数大于最右边数,则左半段是有序的,我们只要在有序的半段里用首尾两个数组来判断目标值是否在这一区域内,这样就可以确定保留哪半边了。
- 此题未考虑含重复元素,当判断nums[mid]=nums[l]=nums[r]时,使用顺序查找即可。
代码
class Solution {
public int search(int[] nums, int target) {
if(nums==null||nums.length==0){
return -1;
}
if(nums.length==1){
return nums[0]==target?0:-1;
}
int l=0;
int r=nums.length-1;
while(l<=r){
int mid=(l+r)/2;
if(nums[mid]==target){
return mid;
}
if(nums[mid]>nums[r]){
if(target>=nums[l]&&target<nums[mid]){//
r=mid-1;
}
else {
l=mid+1;
}
}
else{
if(target>nums[mid]&&target<=nums[r]){//
l=mid+1;
}
else{
r=mid-1;
}
}
}
return -1;
}
}
最新文章
- H5 WebSocket 如何和C#进行通信
- 命令行解析Crash文件
- Django form 中文提交 错误
- SQL笔记 [长期更新] (-2015.4)
- python centos上出现上下键和退格键均为乱码
- Unity3d Realtime Dynamic Volume Clouds Rendering
- android 学习第一步
- poj3685 二分套二分
- 《大数据互联网大规模数据挖掘与分布式处理》阅读笔记(四)-----WEB广告
- IdentityServer Topics(2)- 定义资源
- Java环境变量配置----JDK开发环境及环境变量设置
- Linux下的python3,virtualenv,Mysql、nginx、redis安装配置
- [UWP]使用Picker构建应用内图片公共裁剪组件
- SQL Script for select data from ebs and make a csv file to FTP
- typeof
- 用几分钟了解R语言入门知识
- js 对象的合并(3种方法)转载
- 转:系统吞吐量(TPS)、用户并发量、性能测试概念和公式
- docker 把容器commit成镜像
- 杂项:UN-HTML
热门文章
- SSH 端口转发 - 你不让我看,我也能看
- 【ZJOI 2008】 树的统计 - 树链剖分
- SpringBoot---SpringMVC关于拦截器的一些问题总结
- python的一些使用体会
- Android 重写物理返回键,在h5页面中返回上一个界面
- C++生成元
- VUE 中引入百度地图(vue-Baidu-Map)
- Jmeter 常用函数(21)- 详解 __char
- HDFS的数据流读写数据 (面试开发重点)
- kolla快速集成openstack-ocata和opencontrail-4.0.1.0单节点