LintCode领扣 题解丨微软高频题:搜索旋转排序数组

简介: LintCode领扣 题解丨微软高频题:搜索旋转排序数组

假设有一个排序的按未知的旋转轴旋转的数组(比如,0 1 2 4 5 6 7 可能成为4 5 6 7 0 1 2)。给定一个目标值进行搜索,如果在数组中找到目标值返回数组中的索引位置,否则返回-1。你可以假设数组中不存在重复的元素。

在线评测地址:
https://www.lintcode.com/problem/search-in-rotated-sorted-array/?utm_source=sc-tianchi-sz0827

例1:

输入: [4, 5, 1, 2, 3] and target=1,
输出: 2.
例2:

输入: [4, 5, 1, 2, 3] and target=0,
输出: -1.
【题解】

算法:二分

根据题目我们可以知道旋转数组实际上是两个递增数组的组成,且第一个数组中的最小值大于第二个数组的最大值
由于数组中不存在重复的元素,那么我们可以先找到target在哪个数组,再进行二分
代码思路

二分找到第二个数组的起始位置,即整个数组的最小值的位置minPosition
通过比较target和第二个数组最小元素(即最后一个数)大小关系判断target在哪一个数组
对target所在的数组二分
复杂度分析

N表示为 A 数组的长度

空 间复杂度:O(N)
时间复杂度:O(logN)
public class Solution {

/**
 * @param A: an integer rotated sorted array
 * @param target: an integer to be searched
 * @return: an integer
 */
public int search(int[] A, int target) {
    if (A == null || A.length == 0) { 
        return -1; 
    } 
        
    //找到数组最小值位置minPosition,即第二个数组的起始位置
    int minPosition = 0; 
    intleft = 0; 
    int right = A.length - 1; 
    while (left + 1 < right) { 
        int mid = left + (right - left) / 2; 
        if (A[mid] > A[right]) { 
           left = mid; 
        } else { 
            right = mid; 
        } 
    }         
         
    if (A[left] < A[right]) { 
        minPosition = left; 
    } else { 
        minPosition = right; 
    } 
         
    //判断target在哪一个数组中
    if (A[A.length - 1] < target) { 
        left = 0; 
        right = minPosition - 1; 
    } else { 
        left = minPosition; 
        right = A.length - 1; 
    }
         
    //对target所在数组二分搜索
    while (left + 1 < right) { 
        int mid = left + (right - left) / 2; 
        if (A[mid] < target) { 
            left = mid; 
        } else { 
            right = mid; 
        } 
    }          
        
    if (A[left] == target) { 
        return left; 
    } 
    if (A[right] == target) { 
        return right; 
    }         
    return -1; 
}

}
更多题解参见九章算法官网:
https://www.jiuzhang.com/solution/search-in-rotated-sorted-array/?utm_source=sc-tianchi-sz0827

相关文章
|
3天前
|
弹性计算 人工智能 API
Codex超详细入门指南(下载·安装·登录·上手,全版本覆盖,2026最新版)
建议收藏本教程,2026 全年各版本更新随时回来查阅。如果你在搭建过程中遇到任何问题,欢迎结合 阿里云工单系统 提交技术支持请求,或在 阿里云开发者社区 搜索 Codex 相关话题交流。 祝你编码愉快,效率翻倍!
1651 1
|
6天前
|
JSON 前端开发 API
阿里云最新Qwen4-Max大模型介绍:模型定位、特征、能力、适用场景解析
2026 年 11 月 11 日,阿里发布第四代旗舰模型Qwen4-Max预览版,首发千问 AI 平台 Token Plan,并同步接入千问办公、Qoder 等入口。该版本聚焦知识理解、世界感知、编程与 Agentic 四项升级,主打复杂编程、专业办公、前端设计与专业软件操作。预览期至 11 月 25 日 24:00,到期后模型标识下线;限时 2 折、新用户再享 5 折,最低 1 折可体验。
|
6天前
|
人工智能 前端开发 API
阿里云Qwen4-Max 大模型详解:定位、特征、能力、适用场景与相对Qwen3-Max差异解析
2026年11月11日,阿里发布第四代旗舰模型Qwen4-Max预览版,首发千问AI平台Token Plan并接入千问办公、Qoder等入口。该版本聚焦知识理解、世界感知、编程与Agentic四项升级,主打复杂编程、专业办公、前端设计与专业软件操作等真实任务。预览期为11月11日10:00至11月25日24:00,仅支持Token Plan调用,到期后模型标识下线;限时2折、新用户再享5折,最低1折可体验。
|
3天前
|
Linux Go 开发工具
手机上跑 DeepSeek 智能体:开源安卓客户端 DSH Go 安装与使用指南
DSH Go 是一款开源安卓客户端,将 DeepSeek Harness 智能体引擎装进手机:免 Root、免 Termux,一键安装即用;支持本机运行(内置 Ubuntu+Node.js)或远程接管电脑会话;具备插话打断、过程折叠、屏幕操控、端到端加密分享等特色功能,真正实现智能体“口袋化”。
3007 0
|
19天前
|
Linux 开发工具 iOS开发
Codex保姆级教程(下载+安装+登录+使用,含所有版本,2026最新)
Codex是OpenAI推出的开源AI编程智能体,本地运行,可理解整个代码库,支持自然语言指令改代码、执行命令、跑测试、修Bug,兼容Win/macOS/Linux。(239字)
8498 58
|
13天前
|
Linux 开发工具 iOS开发
2026最新codex下载安装保姆级使用教程(下载+安装+登录+使用,含所有历史版本)
本文详解OpenAI Codex国内快速上手指南:提供Win/macOS/Linux全平台免安装包、npm/Homebrew等多方式安装、账号/API Key双登录、简体中文切换,覆盖下载、安装、汉化、使用及高频避坑(如微软商店失败、npm超时等),10分钟即可跑通。
3025 9
|
19天前
|
JavaScript API iOS开发
DeepSeek Harness下载、安装、配置一篇搞定(2026整理,送常用插件)
DeepSeek Harness(DSH)是DeepSeek于2026年开源的MIT协议AI Agent框架,支持插件化组装模型、工具、沙箱与UI,兼容主流大模型。本文提供免Node.js的桌面端安装包(Win/macOS),含详细图文教程及热门插件推荐。
5808 69
|
7天前
|
云安全 人工智能 安全
|
11天前
|
人工智能 安全 API
DeepSeek Harness下载、安装、配置一篇搞定(2026整理,送常用插件)
DeepSeek Harness(dsh)是DeepSeek AI于2026年开源的轻量级Agent运行框架,基于Cordis内核,践行“一切皆插件”理念。支持Web/桌面双端,开箱即用;内置多模型接入、丰富插件生态(超3.5万),适配编程、办公、创作等场景。(239字)
1912 1