首页 > 其他分享 >力扣 33. 搜索旋转排序数组

力扣 33. 搜索旋转排序数组

时间:2023-04-12 17:11:26浏览次数:48  
标签:target nums 33 mid 力扣 int 数组 排序 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

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/search-in-rotated-sorted-array
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

这道题使用二分查找来解决。由于旋转后的数组实际上可以被划分为两个有序的子数组(因为原数组是升序排列的),所以我们可以通过二分查找的方法,找到数组的中间元素,判断中间元素属于哪个子数组,然后判断目标元素在哪个子数组中,然后递归地在该子数组中进行查找。

我们定义 left 和 right 分别指向数组的左右端点。设数组的中间元素的下标为 mid=(left+right)/2。由于数组被旋转了,因此 nums 数组被分为两个部分 [left,mid] 和 [mid+1,right]。我们考虑以下两种情况:

nums[mid]>=nums[left]:说明中间元素左侧的数组是非旋转数组,右侧的数组是旋转数组。如果目标元素 target 属于非旋转数组,那么在 [left,mid] 中继续查找;否则在 [mid+1,right] 中继续查找。

nums[mid]<nums[left]:说明中间元素右侧的数组是非旋转数组,左侧的数组是旋转数组。如果目标元素 target 属于非旋转数组,那么在 [mid+1,right] 中继续查找;否则在 [left,mid] 中继续查找。

具体实现细节可以参考下面的代码:

include <stdio.h>

include <stdlib.h>

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

int main() {
int nums[] = {4, 5, 6, 7, 0, 1, 2};
int numsSize = sizeof(nums) / sizeof(nums[0]);
int target = 0;
int index = search(nums, numsSize, target);
printf("%d\n", index);
return 0;
}

标签:target,nums,33,mid,力扣,int,数组,排序,left
From: https://www.cnblogs.com/wlxdaydayup/p/17310454.html

相关文章

  • 【图论之拓扑排序】剑指 Offer II 114. 外星文字典
    剑指OfferII114.外星文字典讲解传送门constintN=26,M=N*N;classSolution{public:inth[N],e[M],ne[M],idx=0;boolst[N];intin[N],cnt=0;//上面三行要写在classSolution内部,不然每次调用不会清空voidadd(inta,intb){......
  • 排序算法
    冒泡排序  letarray=[2,5,3,1,4]functionsort(arr){letres=[]if(!Array.isArray(arr))return[]for(vari=0;i<arr.length;i++){for(varj=i+1;j<arr.length;j++){if(arr[i]>arr[j]){lett......
  • ASEMI代理AD9833BRMZ-REEL原装ADI车规级AD9833BRMZ-REEL
    编辑:llASEMI代理AD9833BRMZ-REEL原装ADI车规级AD9833BRMZ-REEL型号:AD9833BRMZ-REEL品牌:ADI/亚德诺封装:MSOP-10批号:2023+引脚数量:10安装类型:表面贴装型AD9833BRMZ-REEL汽车芯片AD9833BRMZ-REEL特征数字可编程频率和相位3V时的12.65mW功耗0MHz至12.5MHz输出频率范围28位分辨率:0.1......
  • UVa 10785 The Mad Numerologist (排序)
    10785-TheMadNumerologistTimelimit:3.000secondshttp://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=98&page=show_problem&problem=1726Numerologyisasciencethatisusedbymanypeopletofindoutamansper......
  • 力扣1113(MySQL)-报告的记录(简单)
    题目:动作表:Actions 此表没有主键,所以可能会有重复的行。action字段是ENUM类型的,包含:('view','like','reaction','comment','report','share')extra字段是可选的信息(可能为null),其中的信息例如有:1.报告理由(areasonforreport)2.反应类型(atypeo......
  • 力扣-数组-螺旋矩阵
     题目顺序59螺旋矩阵Ⅱ,解题思路1.按照num从小到大依次填充,遵循从左到右,从上到下,从右到左,从下到上的层循环顺序;2.层循环中要注意,每个部分保持相同的开闭原则,左闭右开或左开右闭防止混淆出错;3.每层循环的start是不同的;每层循环的每部分个数依次减少;4.注意n的奇偶,奇数单独对中......
  • 力扣1112(MySQL)-每位学生的最高成绩(中等)
    题目:表:Enrollments(student_id,course_id)是该表的主键。问题编写一个SQL查询,查询每位学生获得的最高成绩和它所对应的科目,若科目成绩并列,取course_id最小的一门。查询结果需按student_id增序进行排序。示例Enrollments表:Result表: 建表语句:1CreatetableIf......
  • C语言矩阵顺时针旋转90度和力扣34. 在排序数组中查找元素的第一个和最后一个位置
    #include<iostream>usingnamespacestd;#defineM5#include<stdlib.h>//原矩阵,某元素第n行第m列,;顺时针旋转90度后,位置变成倒数第n列,第m行//即先转置再水平翻转intn=0;voidrotation_90(intmatrix[][M],intn){ for(inti=0;i<n;i++) { for(intj=i;j<M;j++)......
  • 归并排序-使用归并排序实现小和问题-java实现
    什么是归并排序归并排序(MergeSort)是一种基于分治思想的排序算法,它的基本思想是将待排序的序列不断地分割成两个子序列,直到每个子序列只有一个元素,然后再将这两个子序列合并成一个有序的序列。归并排序的基本步骤如下:1.将待排序序列分成两个子序列,分别进行排序。2.将两个已排......
  • w1 洛谷T233243
      主要思路就是计算每一个长度为2的子串出现的次数,计数的同时用数组记录次数,打擂台找到出现次数最多的子串,首字符出现的位置就是数组的下标。最后输出出现最多的子串。代码如下:#include<bits/stdc++.h>usingnamespacestd;intcnt[100];intmain(){ intn,max=-1; ......