博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
14. 二分查找
阅读量:5805 次
发布时间:2019-06-18

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

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

样例

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

 

给一个real耿直的解法

1 int binarySearch(vector
&array, int target) { 2 // write your code here 3 int left=0,right=array.size()-1; 4 int mid; 5 while(left<=right){ 6 mid=left+(right-left)/2; 7 if(target>array[mid]){ 8 left=mid+1; 9 }10 else if(target

第一个else里面是处理几乎快找到解的时候(二分不下去了)会发生的各种情况

1、mid无法取到0或者最后

2、mid是对应target但是不是第一个出现的target

 

转载于:https://www.cnblogs.com/TheLaughingMan/p/8202351.html

你可能感兴趣的文章
Dubbo笔记(四)
查看>>
Web前端JQuery入门实战案例
查看>>
java B2B2C Springboot电子商城系统- SSO单点登录之OAuth2.0 登出流程(3)
查看>>
12月26日云栖精选夜读:CDN新品发布:阿里云SCDN安全加速开放公测
查看>>
USB 通信原理
查看>>
7zZip zip RAR iOS
查看>>
date命令的详细用法!
查看>>
分布式存储ceph集群部署
查看>>
UiAutomator源码分析之UiAutomatorBridge框架
查看>>
python 开发之selenium
查看>>
Xcode3.2.5中找不到Mac OS X - Command Line Utility -...
查看>>
css的div垂直居中的方法,百分比div垂直居中
查看>>
如何理解EM算法
查看>>
nginx 域名跳转一例~~~(rewrite、proxy)
查看>>
linux用户家目录无损迁移到独立硬盘
查看>>
文件查找
查看>>
shell编程前言(一)
查看>>
5、centos7.*配置yum的EPEL源及其它源
查看>>
JSON前后台简单操作
查看>>
shell中一些常见的文件操作符
查看>>