博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
【LintCode 简单】14. 二分查找
阅读量:4088 次
发布时间:2019-05-25

本文共 877 字,大约阅读时间需要 2 分钟。

1.问题描述:

给定一个排序的整数数组(升序)和一个要查找的整数target,用O(logn)的时间查找到target第一次出现的下标(从0开始),如果target不存在于数组中,返回-1

 

2.样例:

在数组 [1, 2, 3, 3, 4, 5, 10] 中二分查找3,返回2

 

3.代码:

class Solution:    # @param nums: The integer array    # @param target: Target number to find    # @return the first position of target in nums, position start from 0     def binarySearch(self, nums, target):        # write your code here        length=len(nums)        start=0        end=length        mid=(end-start)/2        while start<=end:            if nums[mid]
target: end=mid-1 mid=(end-start)/2 else: while nums[mid]==target: mid-=1 return mid+1 return -1

本题是二分查找内容,但是因为测试数组中存在相同的数,需要返回第一个。所以,在二分查找的基础上增加了一些内容。

对于二分查找要注意,当大于或小于时,移动start或end标示:start = mid+1 或 end = mid-1 

当找到target目标值时,通过不断mid-1 来取得第一个target值。

 

 

转载地址:http://jouii.baihongyu.com/

你可能感兴趣的文章
基于云信的react-native聊天系统
查看>>
网易云音乐移动客户端Vue.js
查看>>
ES7 await/async
查看>>
ES7的Async/Await
查看>>
React Native WebView组件实现的BarCode(条形码)、(QRCode)二维码
查看>>
每个人都能做的网易云音乐[vue全家桶]
查看>>
JavaScript专题之数组去重
查看>>
Immutable.js 以及在 react+redux 项目中的实践
查看>>
Vue2.0全家桶仿腾讯课堂(移动端)
查看>>
React+Redux系列教程
查看>>
react-native 自定义倒计时按钮
查看>>
19 个 JavaScript 常用的简写技术
查看>>
ES6这些就够了
查看>>
微信小程序:支付系列专辑(开发指南+精品Demo)
查看>>
iOS应用间相互跳转
查看>>
iOS开发之支付宝集成
查看>>
iOS开发 支付之银联支付集成
查看>>
iOS开发支付集成之微信支付
查看>>
浅谈JavaScript--声明提升
查看>>
React非嵌套组件通信
查看>>