二分查找的讲义和视频

 

源码下载:

https://pan.baidu.com/s/1wMsUK4hZpdttFzOK66n3mQ?pwd=x7a7 提取码 x7a7

先进入《 视频教程及配套源码》,再进入《C++算法》。

在线看视频:

https://www.bilibili.com/video/BV1nL411Q7DY/ 

 

1.1. 基础

1.1.1. 最简单的情况

a. 情况简述

数组已经按升序排好序。

假定要找的数一定存在。

如果存在重复的数,返回任意一个。

b. 原理

如果中间数和目标数相等,返回中间数索引。

如果中间数小于目标数,则目标数一定不在前半部分。

如果中间数大于目标数,则目标数一定不在后半部分。

假定数组区域是左闭右开区间,中间索引=(左索引+右索引)/2

c. 测试数据

04中找1

轮次

待查数据

中间数

第一轮

0 1 2 3 4

2

第二轮

0 1

1

 

15中查找4

轮次

待查数据

中间数

第一轮

1 2 3 4 5

3

第二轮

4 5

5

第三轮

4

4

 

1.1.2. 重复数据返回第一个

a. 情况简述

数组已经按升序排好序。

假定要找的数一定存在。

如果存在重复的数,返回第一个。

b. 原理

如果中间数小于目标数,则目标数一定不在前半部分。

如果中间数大于目标数,则目标数一定不在后半部分。

如果中间数等于目标数,则目标数一定不在后半部分。由于左半部分必须包括中间数,所以左开右闭区间。

c. 测试数据

1,2中寻找2

轮次

待查数据

索引

中间数

第一轮

1 2

(-1,1]

1

第二轮

2

(0,1]

2

 

2,2,3中寻找2

 

轮次

待查数据

索引

中间数

第一轮

2 2 3

(-1,2]

2

第二轮

2 2

(-1,1]

2

第三轮

2

(-1,0]

2

 

2,3,4中寻找2

轮次

待查数据

索引

中间数

第一轮

2 3 4

(-1,2]

3

第二轮

2 3

(-1,1]

2

第三轮

2

(-1,0]

2

1.1.3. 重复数据返回最后一个

a. 情况简述

数组已经按升序排好序。

假定要找的数一定存在。

如果存在重复的数,返回最后一个。

b. 原理

一,如果中间数小于目标数,则目标数一定不在左边、中间,可能在右边。

二,如果中间数大于目标数,则目标数一定不在右边、中间,可能在左边。

三,如果中间数等于目标数,则目标数一定不在左边,可能在中间、右边。

数据

左闭右开

0,1,2,3

0,1

2((0+4)/2)

3

0,1,2

0

1

2

0,1

0

1

 

左开右闭

0,1,2,3

0

1(-1+3)/2

2,3

0,1,2

 

0

1,2

0,1

 

0

1

结论:右(左)开,中间数就和右(左)区间合并,可以保持数据量均衡,左右数量相差不超过1。结合原理三,用左闭右开区间。

 

使用左闭右开(中右合并)后,情况分类

中间数<目标数

中右

>

=

中右

结论:小于等于可以合并

c. 测试数据

 

寻找

期望值

0123

0

0

0123

1

1

0123

2

2

1123

1

1

0113

1

2

 

 

 

 

1.1.4. 循环代替递归

循环结束的条件:元素数量小于2。计算的元素数量可能是0,也可能是负数(非法数据)。由于是二分,所以左右边界一个不变, 一个变成中间位置。

1.1.5. 目标数不一定存在

a. 如果目标数不存在,返回-1

解决方法:返回前,判断是否等于目标值,如果不是返回-1

b. 如果目标数不存在,返回它应该插入的位置

左开右闭

 

数据(寻找0

左右中间索引

1,3,5,7

0,4,2

1,3

0,2,1

1

0,1,0结束

数据(寻找2

左右中间索引

1,3,5,7

0,4,2

1,3

0,2,1

1

0,1结束

数据(寻找4

左右中间索引

1,3,5,7

0,4,2

1,3

0,2,1

3

1,2,1结束

数据(寻找6

左右中间索引

1,3,5,7

0,4,2

5,7

2,4,3

5

2,3,2结束

数据(寻找8

左右中间索引

1,3,5,7

0,4,2

5,7

2,4,3

7

3,4,3结束

规律:

if (vec[left] < iTarget)

{

return left+1;

}

1.1.6. stl二分函数

a. 小于、等于、大于iNum的数

const int iNum = 3;

auto it1 = data.lower_bound(iNum);

auto it2 = data.upper_bound(iNum);

[data.begin(),it1) 表示小于iNum的数。

[it1,it2)表示等于iNum的数。

[it2,data.end()) 表示大于iNum的数。

b. 大于、等于iNum1小于等于iNum2的数

const int iNum1 = 3,iNum2=7;

auto it1 = data.lower_bound(iNum1);

auto it2 = data.upper_bound(iNum2);

视频顺便演示了大于iNum1小于iNum2

c. 对向量二分

const int iNum1 = 3,iNum2=7;

std::sort(data.begin(), data.end());

auto it1 = std::upper_bound(data.begin(), data.end(),iNum1);

auto it2 = std::lower_bound(data.begin(), data.end(), iNum2);

d. 降序

见视频。

e. 通过vector<int>v[1]查找

std::sort(data.begin(), data.end(), [](const std::vector<int>& v1, const std::vector<int>& v2)

{return v1[1] < v2[1]; });

auto it1 = std::lower_bound(data.begin(), data.end(), iNum1, [](const std::vector<int>& v1, int iNum)

{

return v1[1] < iNum;

});

auto it2 = std::upper_bound(data.begin(), data.end(), iNum1, [](int iNum, const std::vector<int>& v2)

{return iNum < v2[1]; });

1.2. 习题

1.2.1. 最大亲密度

有若干包饼干,每包饼干的数量记录在数组nums中,比如:{4,175} ,分配给若干(如:3)小朋友。

每种分配方案的亲密度:任意两个小朋友饼干数的差的绝对值的最小值。

求所有分配方案中的最大亲密度。

分配方案{1,7,5}的亲密度=min(7-1,5-1,7-5}=2

分配方案{4,7,5}的亲密度=min(7-4,5-4,7-5}=1

分配方案{4,1,5}的亲密度=min(4-1,5-4,5-1}=1

分配方案{4,1,7}的亲密度=min(4-1,7-4,7-1)=3

1. 解决思路

先按升序排序。

完成函数is,判断是否存在方案能够满足亲密只大于等于iQinMi

 

因为要找最大值,所以中值符合的时候,抛弃左边。中值跟随右边,用左开右闭。

热门相关:有个人爱你很久   花月颂   前任无双   回眸医笑,冷王的神秘嫡妃   工作女郎