文档章节

[leetcode] Search in Rotated Sorted Array Python

ludlows
 ludlows
发布于 2014/10/07 22:54
字数 164
阅读 15
收藏 0
点赞 0
评论 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 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
Lintcode62 Search in Rotated Sorted Array solution 题解

【题目描述】 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. I......

Winnielyn
06/26
0
0
判断旋转数组中是否含有某个值 Search in Rotated Sorted Array II

问题: Follow up for "Search in Rotated Sorted Array": What if duplicates are allowed? Would this affect the run-time complexity? How and why? Suppose an array sorted in ascendi......

叶枫啦啦
2017/09/17
0
0
153. Find Minimum in Rotated Sorted Array-LeetCode

Question 153. Find Minimum in Rotated Sorted Array Solution 题目大意:给一个按增序排列的数组,其中有一段错位了[1,2,3,4,5,6]变成[4,5,6,1,2,3],把1求出来 思路:遍历,如果当前元素比...

yysue
07/07
0
0
LeetCode 33-Search in Rotated Sorted Array

Problem description Solution Self 看到这个题目,头脑中第一个蹦出来的就是找到rotated的元素,然后两边分别做binary search就可以了。 第一版代码 分两步:1:找到pivot,就是rotated的那...

Quan全
06/21
0
0
Leetcode日记7

(2015/1/2) LeetCode 318 Maximum Product of Word Lengths 题目: 1)求一个字符串数组中,两个不同的字符串的长度乘积的最大值。 2)这两个字符串不能共同拥有同一个字符。(两个字符串的...

fxdhdu
2016/01/03
48
0
Leetcode日记8

(2015/2/3) LeetCode 4 Median of Two Sorted Arrays 题目大意:找到两个已排序数组的median。 median:中间位置的值。 算法: 参考:https://leetcode.com/discuss/15790/share-my-o-log...

fxdhdu
2016/02/18
94
0
决战Leetcode: easy part(1-50)

本博客是个人原创的针对leetcode上的problem的解法,所有solution都基本通过了leetcode的官方Judging,个别未通过的例外情况会在相应部分作特别说明。 欢迎互相交流! email: tomqianmaple@...

qq_32690999
01/25
0
0
android程序员python学习之路

1年半android经验,初次接触python,学了几天,相见恨晚,迫不及待的写了这篇记录下。python新手,请多见谅。 其实也不是最近才接触Python,大四上有一门计算机性能相关的课各种算法、工具要求...

Dynamic_2018
07/08
0
0
搜索旋转的排序数组

原题   Follow up for “Search in Rotated Sorted Array”:   What if duplicates are allowed?   Would this affect the run-time complexity? How and why?   Write a function ......

一贱书生
2016/12/19
5
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

扫码二维码跳转到某个网站

添加maven依赖 <dependency><groupId>com.google.zxing</groupId><artifactId>core</artifactId><version>3.0.0</version></dependency><dependency><groupId>com.goog......

gaomq
8分钟前
0
0
Windows平台下搭建Git服务器的图文教程

Git没有客户端服务器端的概念,但是要共享Git仓库,就需要用到SSH协议(FTP , HTTPS , SFTP等协议也能实现Git共享,此文档不讨论),但是SSH有客户端服务器端,所以在windows下的开发要把自己...

MKChan
14分钟前
0
0
告警系统主脚本&告警系统配置文件&告警系统监控项目

20.20 告警系统主脚本 准备工作 定义监控系统的各个目录,然后再去定义主脚本,因为是分布式的,所以需要每一台机器都需要定义,事先创建好各个脚本和各个目录,随后脚本直接拷贝过去即可,然...

影夜Linux
15分钟前
0
0
谈谈神秘的ES6——(一)初识ECMAScript

谈谈神秘的ES6——(一)初识ECMAScript 在《零基础入门JavaScript》我们就说过,ECMAScript是JavaScript的核心,是JavaScript语法和语义的解释器,同时也是一个标准。而ECMAScript标准其实也...

JandenMa
今天
1
0
第16章 Tomcat配置

16.1 Tomcat介绍 ####Tomcat介绍 LNMP架构针对的开发语言是PHP语言,php 是一门开发web程序非常流行的语言,早些年流行的是asp,在Windows平台上运行的一种编程语言,但安全性差,就网站开发...

Linux学习笔记
今天
0
0
流利阅读笔记29-20180718待学习

高等教育未来成谜,前景到底在哪里? Ray 2018-07-18 1.今日导读 在这个信息爆炸的年代,获取知识是一件越来越容易的事情。人们曾经认为,如此的时代进步会给高等教育带来众多便利。但事实的...

aibinxiao
今天
12
0
OSChina 周三乱弹 —— 你被我从 osc 老婆们名单中踢出了

Osc乱弹歌单(2018)请戳(这里) 【今日歌曲】 @小鱼丁:分享五月天的单曲《后来的我们 (电影《后来的我们》片名曲)》: 《后来的我们 (电影《后来的我们》片名曲)》- 五月天 手机党少年们想...

小小编辑
今天
604
19
Spring Boot Admin 2.0开箱体验

概述 在我之前的 《Spring Boot应用监控实战》 一文中,讲述了如何利用 Spring Boot Admin 1.5.X 版本来可视化地监控 Spring Boot 应用。说时迟,那时快,现在 Spring Boot Admin 都更新到 ...

CodeSheep
今天
5
0
Python + Selenium + Chrome 使用代理 auth 的用户名密码授权

米扑代理,全球领导的代理品牌,专注代理行业近十年,提供开放、私密、独享代理,并可免费试用 米扑代理官网:https://proxy.mimvp.com 本文示例,是结合米扑代理的私密、独享、开放代理,专...

sunboy2050
今天
0
0
实现异步有哪些方法

有哪些方法可以实现异步呢? 方式一:java 线程池 示例: @Test public final void test_ThreadPool() throws InterruptedException { ScheduledThreadPoolExecutor scheduledThre......

黄威
今天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部