原始碼下載：
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. 測驗資料
從0到4中找1，
|
輪次 |
待查資料 |
中間數 |
|
第一輪 |
0 1 2 3 4 |
2 |
|
第二輪 |
0 1 |
1 |
從1到5中查找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,1，7，5} ,分配給若干（如：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，
因為要找最大值，所以中值符合的時候，拋棄左邊，中值跟隨右邊，用左開右閉，
2021年目標：完成新書《聞缺陷則喜》,本博客右上公告有下載、閱讀鏈接，轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/556384.html
標籤：其他
上一篇：二分查找的講義和視頻
下一篇：返回列表