`

Leetcode - Search in Rotated Sorted Array

 
阅读更多
[分析] 这题可以看做是Find Minimum in Rotated Sorted Array 的扩展,思路仍然是二分,若mid 元素正好是target,皆大欢喜找到了,否则就需要进一步推理target 如果在数组中存在应该在左半边还是右半边,推理思路是:若左边界元素小于mid元素,说明左半边是升序的,查看左边界是否是target,否则若target 落在左边界和mid元素限定的范围内则继续搜左半边,否则搜右半边;若左边界大于mid元素,说明右半边是升序的,类似处理。

[ref]
http://blog.csdn.net/linhuanmars/article/details/20525681

public class Solution {
    public int search(int[] A, int target) {
        if(A == null || A.length < 1)        
            return -1;
        
        int lp = 0, rp = A.length - 1;
        while(lp <= rp){
            int mid = lp + ((rp - lp) >> 1);
            if(A[mid] == target)
                return mid;
            if(A[mid] > A[lp]){
                if(A[lp] == target)
                    return lp;
                else if(A[lp] < target && target < A[mid])
                    rp = mid - 1;
                else
                    lp = mid + 1;
            }else{
                if(A[rp] == target)
                    return rp;
                else if(A[mid] < target && target < A[rp])
                    lp = mid + 1;
                else
                    rp = mid - 1;
            }
        }
        return -1;
    }
}
分享到:
评论

相关推荐

    js-leetcode题解之33-search-in-rotated-sorted-array.js

    【js-leetcode题解之33-search-in-rotated-sorted-array.js知识点】 1. 题目分析:题目"search-in-rotated-sorted-array"要求在旋转排序数组中搜索一个指定的目标值。数组原本是升序排列的,但是经过旋转后,其排序...

    c语言-leetcode题解之0081-search-in-rotated-sorted-array-ii.zip

    在LeetCode的题库中,编号为0081的题目名为“Search in Rotated Sorted Array II”,这是一道中等难度的算法题。题目描述的是在一个经过旋转排序的数组中搜索特定的元素,这个问题与传统的二分查找问题有一定的相似...

    python-leetcode题解之081-Search-in-Rotated-Sorted-Array-II

    python python_leetcode题解之081_Search_in_Rotated_Sorted_Array_II

    C语言-leetcode题解之33-search-in-rotated-sorted-array.c

    今天我们要讨论的是一个在LeetCode平台上非常热门的算法题目——在旋转排序数组中搜索目标值,对应的C语言解法源文件为"33-search-in-rotated-sorted-array.c"。 首先,这个题目的背景是在一个原本有序的数组,经过...

    js-leetcode题解之81-search-in-rotated-sorted-array-ii.js

    《LeetCode题解之81-在旋转排序数组中搜索二.js》的知识点详细解析如下: 1. **数组旋转概念解析**: 在数组中应用旋转操作,即选择一个旋转点,将数组分割成两部分,然后将后半部分移动到数组的前面。例如,[4,5,...

    python-leetcode题解之154-Find-Minimum-in-Rotated-Sorted-Array-II.py

    这种问题在LeetCode上被称为“Find Minimum in Rotated Sorted Array II”,是数组、二分查找以及算法复杂度分析等计算机科学基础知识点的具体应用。掌握此类问题的解决方法,对于提高编程能力和算法思维都大有裨益...

    js-leetcode题解之153-find-minimum-in-rotated-sorted-array.js

    在JavaScript中解决LeetCode题号为153的“寻找旋转排序数组中的最小值”问题,要求对一个按照升序排列的数组进行旋转后的数组寻找其中的最小值。这个问题可以通过二分查找算法来高效解决。具体来讲,算法的核心在于...

    python-leetcode题解之153-Find-Minimum-in-Rotated-Sorted-Array.py

    在解决leetcode上第153题“寻找旋转排序数组中的最小值”时,一个高效的算法是使用二分查找。这道题目的难点在于输入数组是经过旋转的排序数组,即部分元素被移到了数组的末尾,但它仍然保持了部分排序特性。这类...

    js-leetcode题解之154-find-minimum-in-rotated-sorted-array-ii.js

    在JavaScript中,解决LeetCode第154题“寻找旋转排序数组中的最小值 II”是一个经典的算法问题。此题要求在O(logn)时间复杂度内找到一个经过旋转的排序数组中的最小值。由于数组可能有重复元素,并且可以包含重复的...

    扔鸡蛋leetcode-LeetCode-Note-Mary:玛丽的leetcode笔记本

    Search in Rotated Sorted Array(搜索旋转排序数组)#数组 2020/12/08 19. Remove Nth Node From End of List(删除链表的倒数第N个节点) 153. Find Minimum in Rotated Sorted Array(寻找旋转排序数组中的最小值...

    _leetcode-python.pdf

    - Search in Rotated Sorted Array II: 假设按照升序排序的数组在预先未知的某个点上进行了旋转,该问题要求在旋转后的数组中搜索特定元素。 这些知识点涵盖了数据结构和算法的核心概念,以及如何用Python语言实现...

    lrucacheleetcode-leetcode-in-go:leetcode-in-go

    find-minimum-in-rotated-sorted-array-0153 数组的乘积-除了-self-0238 从排序数组中删除重复项-0026 搜索旋转排序数组-0033 两个整数之和-0371 二和-0001 回溯 组合-和-0039 组合总和-ii-0040 电话号码的字母组合 ...

    leetcode-cpp刷题

    - **2.1.3 Search in Rotated Sorted Array** - 给定一个旋转后的有序数组,找到某个元素的位置。 - 实现思路:利用二分查找法,在处理中间值时考虑数组旋转的情况。 - **2.1.4 Search in Rotated Sorted Array ...

    leetcode卡-Array-LeetCode-Solution:数组-LeetCode-解决方案

    7. **二分查找**:在已排序的数组中查找特定元素或满足条件的元素,如"搜索旋转排序数组"(Search in Rotated Sorted Array)。 8. **位运算**:在数组操作中,位运算有时能提供高效的解决方案,如"无重复字符的...

    颜色分类leetcode-leetcode-[removed]我对Leetcode问题的解决方案

    颜色分类leetcode My Leetcode Problems Solutions Using javascript(ES6) 1 Two Sum 两数之和 5 Longest Palindromic Substring 最长回文子串 7 Reverse Integer 整数反转 9 Palindrome Number 回文数 11 Container...

    算法刷题笔记leetcode/lintcode

    - Search in Rotated Sorted Array II(在旋转排序数组中搜索II) - Find Minimum in Rotated Sorted Array(在旋转排序数组中寻找最小值) - Find Minimum in Rotated Sorted Array II(在旋转排序数组中寻找...

    算法-leetcode-剑指offer上的题很多

    - **在旋转排序数组中搜索 II/Search in Rotated Sorted Array II**: 当数组中存在重复元素时,在被旋转过的排序数组中搜索给定数字。 #### 高级算法技巧 - **数学与位操作(Math and Bit Manipulation)**: 利用数学...

    leetcode296-leetcode-in-py-and-go:Go中的Leetcode

    search-in-rotated-sorted-array ,比较中间值和边,而不是目标和边 40:combination-sum-ii:传递最后选择的索引 41:先缺失正,交换 42:只是提醒:块 - 垃圾箱 43:多字符串,i+j,i+j+1 44:通配符

    leetcodelintcode差异-leetcode-python:leetcode-python

    leetcode lintcode差异 leetcode-python 九章算法基础班 二分 题目 地址 153. Find Minimum in Rotated Sorted Array 双指针 题目 Solution Tag LintCode 604. Window Sum LeetCode 283. Moves Zeroes Array、Two ...

Global site tag (gtag.js) - Google Analytics