首页 > 其他分享 >旋转数组 二分查找变种

旋转数组 二分查找变种

时间:2023-12-15 20:45:32浏览次数:36  
标签:二分 target nums 变种 mid 查找 数组 left

题目

搜索旋转排序数组
整数数组 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
示例 2:

输入:nums = [4,5,6,7,0,1,2], target = 3
输出:-1
示例 3:

输入:nums = [1], target = 0
输出:-1

提示:

1 <= nums.length <= 5000
-104 <= nums[i] <= 104
nums 中的每个值都 独一无二
题目数据保证 nums 在预先未知的某个下标上进行了旋转
-104 <= target <= 104
相关标签

C++

作者:LeetCode
链接:https://leetcode.cn/leetbook/read/top-interview-questions-medium/xvyz1t/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

答案

int search(vector& nums, int target) {
int left = 0 , right = nums.size() -1;
int mid;
while(left <= right){
mid = left + (right - left) / 2;
if(nums[mid] == target){
return mid;
}
if(nums[left] <= nums[mid]){
if(target >= nums[left] && target < nums[mid]){
right = mid -1;
}
else{
left = mid + 1;
}
}
else{
if(target > nums[mid] && target <= nums[right]){
left = mid + 1;
}
else{
right = mid -1;
}
}
}

return -1;

}

关键

关键在于二分查找组合进旋转数组,先找到需要的数组再去二分,多次二分达到logn

标签:二分,target,nums,变种,mid,查找,数组,left
From: https://www.cnblogs.com/minipython-wldx/p/17904140.html

相关文章

  • 洛谷P1824 进击的奶牛 题解 二分答案
    题目链接:https://www.luogu.com.cn/problem/P1824题目大意:本题相当于在\(n\)个数中选\(c\)个数,使得这\(c\)个数中相差最小的两个数之差尽可能地大。解题思路:我们首先可以给\(a_1\sima_n\)从小到大排一下序(这里有点贪心的思想,你会发现很多涉及贪心的问题在排序之后解......
  • python二分类模型精度低怎么办
    在二分类模型中,如果模型的精度较低,可能需要采取一些措施来改进模型性能。本文将介绍一些常见的方法和技巧,帮助提高二分类模型的精度。1.数据预处理确保对数据进行适当的预处理是提高模型精度的重要步骤。常见的数据预处理方法包括:-数据清洗:处理缺失值、异常值等。-特征选择:选择对目......
  • 线性探测法的查找函数 整型关键字的散列映射
    一、 实验目的掌握哈希表二、  实验内容实验题目线性探测法的查找函数整型关键字的散列映射  三、   设计文档 1.   2.   四、   源程序  1. PositionFind(HashTableH,ElementTypeKey){    intflag=0;    Positionp......
  • 线性探测法的查找函数
    #include<stdio.h>#defineMAXTABLESIZE100000/*允许开辟的最大散列表长度*/typedefintElementType;/*关键词类型用整型*/typedefintIndex;/*散列地址类型*/typedefIndexPosition;/*数据所在位置与散列地址是同一类型*//*散列单元状态类......
  • 查找列表(表格的列名)是否包含某些列名字符串
    lis=["非关键词","关键词1","/s关键词2/s","重复的关键词1"]keywords=["关键词1","关键词2","关键词3"]result={}foriinkeywords:find=Falseforj,kinenumerate(lis):ifnotfind:......
  • Excel 公式SWITCH函数你用过吗?多种查找函数介绍
    我们公司的项目上的模板使用了Excel的Switch函数,今天我使用的时候,发现报错,无法使用。环境说明我使用的是Windows10专业版,Office2016报错信息在Excel中的报错如下: 单元格的公式如下:=F8*_xlfn.SWITCH(H8,"高",1.5,"中",1,"低",0.5)*(100-I8)/100 查找问题从网上找了......
  • 代码随想录算法训练营第一天|704.二分查找、27.移除元素
    LeetCode704二分查找题目链接704.二分查找二分法确定区间(循环不变量):对于有序数组,定义循环区间二分查找元素 LeetCode27.移除元素题目链接:27.移除元素快慢指针,快指针查,慢指针存 ......
  • 代码随想录算法训练营第一天 | 数组理论基础,704. 二分查找,27. 移除元素
    一、数组理论基础学习前:1.数组定义一些在内存上连续存储的相同数据类型的数据的集合2.数组特征便于查询数组元素,不便于增删数据元素学习后:对于Java,二维数组不一定在内存上连续。如int[i][j],唯一确定的是int[i][]在内存上连续二、704.二分查找LeetCode704.二分查找......
  • 代码随想录算法训练营第一天| LeetCode704 二分查找、27移除元素
     Leetcode704:二分查找今日学习的文章链接:代码随想录(programmercarl.com) 题目链接:704.二分查找-力扣(LeetCode)●  自己看到题目的第一想法这题我会,但是还没明白卡尔说的循环不变量是什么意思。我的固定思路就是,target比中间值大,左指针右移到mid+1;target比中间值......
  • 算法学习Day1,二分查找,移除元素
    Day1二分查找,移除元素ByHQWQF2023/12/13笔记704.二分查找给定一个n个元素有序的(升序)整型数组nums和一个目标值target,写一个函数搜索nums中的target,如果目标值存在返回下标,否则返回-1。解法:使用二分查找来在一个有序的数组中找到指定元素的下标。根据数据边界......