旋转数组的查找

男娘i 2024-02-19 20:59 5阅读 0赞

一、题目

给定一个有序数组，如\{1,2,3,4,5,6,7,8,9\}，我们将对这个数组进行选择，位置旋转未知。下面给出一个可能的旋转结果。如\{4,5,6,7,8,9,1,2,3\}，我们可以理解为它从元素4位置开始旋转。之后给定一个指定的数字n，让我们从\{4,5,6,7,8,9,1,2,3\}这个数组中找出它的位置，要求时间复杂度尽可能的低。

二、解析

二分查找的变形.

思路： 1、选择中间点mid作为拐点

2、确定数组哪一边有序

3、判断目标值与中间值以及与开始元素的关系

三、代码实现

class Solution {
        public int search(int[] nums, int target) {
            int start = 0, end = nums.length-1;
            while(start <= end){
                if(target == nums[start]) return start;
                if(target == nums[end]) return end;
     
                int middle = (start + end)/2;
                if(target == nums[middle])
                    return middle;
     
                if(nums[start] > nums[middle]){//右边有序
                    if(target > nums[middle] && nums[start] > target)
                        start = middle + 1;
                    else
                        end = middle - 1;
                } else {
                    if(target < nums[middle] && target > nums[start])
                        end = middle - 1;
                    else
                        start = middle + 1;
                }
            }
     
            return -1;
        }
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，5人围观）

还没有评论，来说两句吧...

相关阅读

相关旋转数组的查找

一、题目给定一个有序数组，如\{1,2,3,4,5,6,7,8,9\}，我们将对这个数组进行选择，位置旋转未知。下面给出一个可能的旋转结果。如\{4,5,6,7,8,9,1

男娘i/ 2024年02月19日 20:59/ 0 赞/ 6 阅读

相关旋转数组的最小数字 - 二分查找

旋转数组的最小数字把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 \[3,4,5

妖狐艹你老母/ 2022年12月17日 08:45/ 0 赞/ 130 阅读

相关 java旋转数组查找某一个值_剑指offer java -查找旋转数组的最小数字

/\\ \ Created by wqc on 2017/7/18. \ 查找旋转数组的最小数字 \ 把一个数组最开始的若干个元素搬到数组的末尾，称为数组的旋转 \ 输

àì夳堔傛蜴生んèń/ 2022年11月07日 05:55/ 0 赞/ 117 阅读

相关旋转数组的最小数字

题目描述把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。例如数组\{3,4,5,1,2\

谁践踏了优雅/ 2022年07月16日 04:21/ 0 赞/ 146 阅读

相关旋转数组的最小数字

时间限制：`3秒` 空间限制：`32768K` 热度指数：`199704` 本题知识点： `查找` 题目描述把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组

╰半橙微兮°/ 2022年06月08日 02:42/ 0 赞/ 151 阅读

相关旋转数组的最小数字

链接： [https://www.nowcoder.com/questionTerminal/9f3231a991af4f55b95579b44b7a01ba][https_w

古城微笑少年丶/ 2022年06月07日 11:51/ 0 赞/ 146 阅读

相关【Python】查找旋转数组的最小值

查找旋转数组的最小值 > 假定一个排序数组以某个未知元素为支点做了旋转，如：原数组0 1 2 4 5 6 7旋转后得到4 5 6 7 0 1 2。请找出旋转后数组的最小值

爱被打了一巴掌/ 2022年05月22日 08:26/ 0 赞/ 134 阅读

相关旋转数组的最小数字

[旋转数组的最小数字][Link 1] 题目描述把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非减排序的数组的一个旋转，输出旋转数组

刺骨的言语ヽ痛彻心扉/ 2022年03月25日 15:18/ 0 赞/ 162 阅读

相关【剑指Offer】（数组）旋转数组的最小数字（二分查找）

题目链接：[https://www.nowcoder.com/practice/9f3231a991af4f55b95579b44b7a01ba?tpId=13&tqId=11

﹏ヽ暗。殇╰゛Y/ 2022年03月16日 12:48/ 0 赞/ 188 阅读

相关旋转数组的最小数字

时间限制：3秒空间限制：32768K 热度指数：481834 本题知识点：查找算法知识视频讲解题目描述把一个数组最开始的若干个元素搬到数组的末尾，我们

怼烎@/ 2022年03月12日 08:10/ 0 赞/ 176 阅读