文档章节

[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 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
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
08/10
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
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

没有更多内容

加载失败,请刷新页面

加载更多

Dubbo分析之Cluster层

系列文章 Dubbo分析Serialize层 Dubbo分析之Transport层 Dubbo分析之Exchange 层 Dubbo分析之Protocol层 前言 紧接上文Dubbo分析之Protocol层,本文继续分析dubbo的cluster层,此层封装多个提...

ksfzhaohui
30分钟前
2
0
linux Ubuntu 安装 hyperledger fabric

一、apt-get update 二、安装docker sudo apt-get install docker.io 如果安装报错:E: Unable to locate package,请执行第一条。 # docker -v Docker version 1.6.2, build 7c8fca2 # dock......

八戒八戒八戒
33分钟前
2
0
神经网络基础及Keras入门

神经网络定义 人工神经网络,简称神经网络,在机器学习和认知科学领域,是一种模仿生物神经网络(动物的中枢神经系统,特别是大脑)的结构和功能的数学模型或计算模型,用于对函数进行估计或...

Python女神
34分钟前
1
0
Pycharm上Django的使用 Day9

编辑条目: 1.创建edit_entry的URL模式 形参entry_id存储在URL中传递的ID,这个URL模式将预期匹配的请求发送给视图函数edit_entry() 2.编写视图函数edit_entry() 1处获取用户要修改的条目对象...

不会TC的猫
34分钟前
1
0
夹点getGripPoints/捕捉点getOsnapPoints

已知圆外一点,以及圆心半径,求圆的切点: 方法1: (b-y/a-x)*(n-y/m-x)=-1(a-x)平方+(b-y)平方=r平方联立方程组求解 方法1: CPoint CalcQieDian(CPoint ptCenter, CPoint ptOutside, do...

一个小妞
46分钟前
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部