二分查找
二分查找
二分查找基本思路与模板
文章图片
image
def binary_search(l , r): # 模板一：寻找右区间的左端点(上图红色部分)while l < r:
mid = (l+r)//2 # 注意 l+rif check(mid): r = mid// check(mid) 为truemid对应的值>=target
else: l = mid+1def binary_search(l , r): # 模板二：寻找左区间的右端点（上图蓝色部分）while l < r:
mid = (l+r+1)//2 # 注意 l+r+1if check(mid): l = mid // check(mid) 为truemid对应的值<=targetelse: r = mid-1
大致可以分为寻找左边的最后一个（左区间的右端点）、右边的第一个（右区间的左端点）。
注意点：
//右区间的左端点，为什么是(l+r)/2
模板一： mid = (l+r)/2;
r = mid;
l = mid+1//左区间的右端点 为什么是(l+r+1)/2
模板二：mid = (l+r+1)/2;
l = mid;
r = mid-1
【二分查找】在模板一情况下，
当区间收缩到[i,i+1]时
若 mid=（l+r+1）/2，即mid=(i+i+1+1)/2=i+1 那么check(mid)为true，则
r=mid=i+1,区间为[i，i+1]，则进入死循环。
在模板二情况下，
当区间收缩到[i,i+1]时，
若 mid= (l+r)/2, 即mid=(i+i+1)/2=i+1/2=i 那么check(mid)为true，则
l=mid=i ，区间为[i,i+1],进入死循环。
一个简单的示例：
const data=https://www.it610.com/article/[1,2,4,6,6,7,8,9,9,9,9,23,56,88,100];
// 右区间的第一个数function test1(num,data){let i=0;
let j=data.length-1;
while(i=target){
return true;
}else{
return false;
}
}console.log("右区间",test1(9,data))//左区间 最后一个数function test2(num,data){
let i=0;
let j=data.length-1;
while(i 参考 二分法
推荐阅读
- 超好用的PubMed文献查找管理插件—Scholarscope
- Elasticsearch|Elasticsearch 简介
- 1月尾，是2018年的十二分之一，陈先生自我独白
- 终极找 bug 大法 - 二分
- iOS|iOS Runtime 的方法缓存（存储的形式、数据结构以及查找的过程？）
- 算法|算法-二分查找
- 128
- Python笔记关于环境安装（二）模块的查找
- Python|Python 每日一练 二分查找 搜索旋转排序数组 详解
- Mysql配置问题