我這篇文章要講的一道算法題憨愉，一點都不難兼吓，可以說是小白級別的臂港，是關(guān)于一個數(shù)組中計算某個元素的重復(fù)個數(shù)的問題。
具體問題：看如下一個無序的數(shù)組，求其中數(shù)字2出現(xiàn)的次數(shù)审孽。怎么樣县袱，是不是超級簡單：）
[0,2,1,1,2,3,5,2,3,3,4,5,7,6,2]
能夠想到的解法，直接一趟for循環(huán)佑力，碰到元素等于2了就開始計數(shù)加一式散，2的個數(shù)就是計數(shù)值。
挺好打颤。這肯定能解決問題暴拄。
下面給出上面思路的實現(xiàn)，使用c++代碼编饺。值得注意的是乖篷，這里應(yīng)該使用c++中的模板，也就是通常說的泛型透且。因為那伐，我們并不確定給定數(shù)組元素的具體類型，除了上面給出的數(shù)組元素是整數(shù)外石蔗，也可能是字符串，或者自定義對象畅形。
template <typename T>
int countOccurrences(vector<T> arr, T target){
int result = 0;
for (int i = 0; i < arr.size(); i++) {
if (target == arr[i]) {
result++;
}
}
return result;
}
還有沒有其他方法呢养距？這個時候就可以想一下，對了日熬，我們也可以使用查找表來解決這個問題棍厌，以元素值為鍵，值為數(shù)組中相同元素的個數(shù)竖席。需要一趟for 循環(huán)來統(tǒng)計相同元素的個數(shù)耘纱，最后返回這個查找表中對應(yīng)元素的值就好了。
給出代碼：
template <typename T>
int countOccurrences(vector<T> arr, T target){
unordered_map<T, int> map;
for (int i = 0; i < arr.size(); i++) {
map[arr[i]]++;
}
return map[target];
}
想一想毕荐，如果這個數(shù)組變成有序了束析？可以想到其他方法來解決這個問題嗎？
[0,1,1,2,2,2,2,3,3,3,4,5,5,6,7]
此時就可以使用二分查找了憎亚，二分查找主要解決的就是有序集合的查找問題员寇。可是問題來了第美，這里有4個2蝶锋，二分查找只能找到其中的一個2，這....好像使用二分查找也不行吧什往。
如果有這個疑問扳缕，可以先按照二分查找的思路，停下來先思考下如何使用二分查找來解決這個問題。
繼續(xù)躯舔。
其實驴剔，我們可以使用二次二分查找，第一次尋找的是查找值的左邊界庸毫，第二次尋找的是查找值的右邊界仔拟。
先給出代碼，然后根據(jù)代碼進行講解飒赃。
template <typename T>
int countOccurrences(vector<T> arr, T target){
int low_left = 0;
int high_left = arr.size();
while (low_left < high_left) {
int middle = low_left + (high_left - low_left) / 2;
if (arr[middle] < target) {
low_left = middle + 1;
} else {
high_left = middle;
}
}
int low_right = 0;
int high_right = arr.size();
while (low_right < high_right) {
int middle = low_right + (high_right - low_right) / 2;
if (arr[middle] > target) {
high_right = middle;
} else {
low_right = middle + 1;
}
}
return low_right - low_left;
}
我準備根據(jù)程序運行的邏輯利花，一步步進行講解。
首先载佳，這是我們傳入的數(shù)組炒事，尋找2的重復(fù)元素
vector<int> vec = vector<int>{0,1,1,2,2,2,2,3,3,3,4,5,5,6,7};
int result = countOccurrences(vec, 2);
第一個循環(huán)的作用是尋找左邊界，也就是2起始的索引蔫慧，在第一個while循環(huán)前挠乳，設(shè)置兩個變量，low_left,high_left,我對這兩個值的定義是在區(qū)間 [low_left,high_left) 中尋找目標值姑躲，注意區(qū)間是前閉后開的,所以這兩個值的初始值設(shè)置為 low_left = 0,high_left = arr.size()睡扬。
經(jīng)過第一個循環(huán)，中間值middle = 7黍析，arr[7] = 3, 3大于2卖怜，所以此時 high_right = 7，數(shù)組如下所示阐枣，high_left此時指向3马靠。為了便于查看，#號表示low_left的位置蔼两，*號表示high_left的位置甩鳄。
[0,1,1,2,2,2,2,3,3,3,4,5,5,6,7]
# *
繼續(xù)第二次循環(huán)，中間值middle = 3,arr[3] = 2,2等于目標值额划，所以此時high_left = 3,所以在這里也可以看出這里用到的二分查找與一般的二分查找的區(qū)別了妙啃，一般的二分查找在找到目標值后就會結(jié)束循環(huán)，這里卻不然俊戳，會繼續(xù)向左邊部分查找彬祖。因為我們要找的是2第一次出現(xiàn)的位置。
[0,1,1,2,2,2,2,3,3,3,4,5,5,6,7]
# *
繼續(xù)第三次循環(huán)品抽，中間值middle = 1,arr[1] = 1,1小于2储笑，所以此時low_left = middle + 1,就應(yīng)該等于2。
[0,1,1,2,2,2,2,3,3,3,4,5,5,6,7]
# *
繼續(xù)第四次循環(huán)圆恤，middle = 2 + (3 - 2) / 2 = 2, arr[2] = 1, 1小于2突倍，所以此時low_left繼續(xù)加一腔稀，low_left = 3,結(jié)束循環(huán)。這個時候羽历，我們就找到了2第一次出現(xiàn)的位置焊虏，如圖。
[0,1,1,2,2,2,2,3,3,3,4,5,5,6,7]
#
*
尋找右邊界與左邊的邏輯類似秕磷，給出圖示诵闭，就不一一講解了，與尋找左邊界不同的是澎嚣，在找到2之后疏尿，會繼續(xù)向右查找，2結(jié)束的位置易桃。
[0,1,1,2,2,2,2,3,3,3,4,5,5,6,7]
# *
[0,1,1,2,2,2,2,3,3,3,4,5,5,6,7]
# *
[0,1,1,2,2,2,2,3,3,3,4,5,5,6,7]
# *
[0,1,1,2,2,2,2,3,3,3,4,5,5,6,7]
# *
[0,1,1,2,2,2,2,3,3,3,4,5,5,6,7]
#
*
查找到的結(jié)果右邊界是索引在7的位置褥琐，所以2出現(xiàn)的次數(shù)是右邊界減去左邊界，也就是7減去3等于4晤郑，求出結(jié)果敌呈。
接下來討論一種特殊情況。
當(dāng)前數(shù)組中不包括需要查找的元素造寝。那么此時low_right 和 low_left 會返回相同的數(shù)磕洪，兩數(shù)相減等于零，是滿足的诫龙，
總結(jié)一下褐鸥，在這個方法中，查找到值后赐稽，并不會停止查找，而是繼續(xù)向左或向右浑侥，找到目標值的起始位置和結(jié)束位置姊舵。可以看到寓落，在掌握基本知識的基礎(chǔ)上括丁，能靈活運用是非常重要的。
