文档章节

[leetcode] Search in Rotated Sorted Array Python

ludlows
 ludlows
发布于 2014/10/07 22:54
字数 164
阅读 18
收藏 0

Problem:

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

解题关键:在于确定mid位于转折点之前,还是之后

solution:

class Solution:
    # @param A, a list of integers
    # @param target, an integer to be searched
    # @return an integer
    def search(self, A, target):
        low = 0 
        high = len(A)
    
        while high != low:
            mid = (low+high)/2
            if A[mid] == target:
                return mid
            if A[low] < A[mid]:
                if target<A[mid] and A[low] <= target:
                    high = mid
                else:
                    low += 1
            else:
                if A[mid] < target and target <= A[high-1]:
                    low = mid + 1
                else:
                    high = mid
        return -1



© 著作权归作者所有

共有 人打赏支持
ludlows
粉丝 0
博文 15
码字总数 4195
作品 0
海淀
程序员
私信 提问
LeetCode--旋转有序数组大总结

我们知道在一段有序的数组里面查找某一个数字时可以使用二分查找算法来实现o(lgn)时间复杂度的查找,现在题目给我们的数组是有序数组的旋转。比如原数组为(1,2,3,4,5,6,7),旋转后可能变成...

CLthinking
2018/12/21
0
0
Leetcode 33. Search in Rotated Sorted Array

文章作者:Tyan 博客:noahsnail.com | CSDN | 简书 1. Description 2. Solution Reference https://leetcode.com/problems/search-in-rotated-sorted-array/description/......

SnailTyan
2018/08/09
0
0
Leetcode 81. Search in Rotated Sorted Array II

文章作者:Tyan 博客:noahsnail.com | CSDN | 简书 1. Description 2. Solution Reference https://leetcode.com/problems/search-in-rotated-sorted-array-ii/description/......

SnailTyan
2018/08/10
0
0
Leetcode(153) Find Minimum in Rotated Sorted Array

Leetcode上的一道题。在rotated array中找到最小值。一个rotated array就是一个已排序好的数组绕着某个位置旋转180度,像[1,2,3,4,5,6],绕着5旋转后就是[5,6,1,2,3,4]。 用二分法找最小值,...

mambakb
2018/12/05
0
0
LeetCode Question Difficulty Distribution 问题难度和频率分布

Leetcode问题难度和频率分布表 引用自: https://zephyrusara.blogspot.jp/2014/07/leetcode-question-difficulty.html LeetCode Question Difficulty Distribution : Sheet1......

xidiancoder
2017/09/10
0
0

没有更多内容

加载失败,请刷新页面

加载更多

OSChina 周一乱弹 —— 白掌柜说了卖货不卖身

Osc乱弹歌单(2019)请戳(这里) 【今日歌曲】 @爱漫爱 :这是一场修行分享羽肿的单曲《Moony》 手机党少年们想听歌,请使劲儿戳(这里) @clouddyy :开不开心? 开心呀, 我又不爱睡懒觉…...

小小编辑
今天
8
0
大数据教程(11.7)hadoop2.9.1平台上仓库工具hive1.2.2搭建

上一篇文章介绍了hive2.3.4的搭建,然而这个版本已经不能稳定的支持mapreduce程序。本篇博主将分享hive1.2.2工具搭建全过程。先说明:本节就直接在上一节的hadoop环境中搭建了! 一、下载apa...

em_aaron
今天
3
0
开始看《JSP&Servlet学习笔记》

1:WEB应用简介。其中1.2.1对Web容器的工作流程写得不错 2:编写Servlet。搞清楚了Java的Web目录结构,以及Web.xml的一些配置作用。特别是讲了@WebServlet标签 3:请求与响应。更细致的讲了从...

max佩恩
今天
4
0
mysql分区功能详细介绍,以及实例

一,什么是数据库分区 前段时间写过一篇关于mysql分表的的文章,下面来说一下什么是数据库分区,以mysql为例。mysql数据库中的数据是以文件的形势存在磁盘上的,默认放在/mysql/data下面(可...

吴伟祥
今天
3
0
SQL语句查询

1.1 排序 通过order by语句,可以将查询出的结果进行排序。放置在select语句的最后。 格式: SELECT * FROM 表名 ORDER BY 排序字段ASC|DESC; ASC 升序 (默认) DESC 降序 1.查询所有商品信息,...

stars永恒
今天
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部