Binary Search & Ternary Search & 實作misc

例題：

給一長度為 \(n\) 的已排序陣列 \(a\)，以及 \(m\) 個詢問，問你 \(x\) 是否在 \(a\) 之中。

做法一：

每次遍歷過整個陣列看 \(x\) 是否在 \(a\) 之中
複雜度：\(O(n)\)

做法二：

可以用陣列已排序的性質，二分搜陣列。

可以觀察到如果一個數字 \(d\) 在陣列中比 \(x\) 小， \(x\) 如果有出現在陣列中，就一定在 \(d\) 的右邊。
如果善用這個性質，每次就可以將搜索區間減少一半。

下面我們示範一下
在 \([1, 3, 5, 7, 9, 11, 13, 15, 17, 19]\) 上詢問 \(15\) 是否在陣列內

做法二：

一開始整個陣列都是有可能的範圍，所以

 int l = 1, r = 10;

做法二：

看中間的位置是不是我們要的答案

 int mid = (l + r) / 2; // mid = 5

做法二：

發現不是而且發現 \(arr[mid]\) 小於等於 \(15\)，所以左邊的區間不會有 \(15\)，因此我們將 \(left\) 移到 \(mid\) 的位置

 if(arr[m] <= tar) {
	l = m;
}

做法二：

接下來就一樣，
看中間的位置是不是我們要的答案

做法二：

找到答案了！

做法二：

雖然這個範例沒有出現，但如果 \(arr[mid]\) 大於 \(15\) 時，\(mid\) 的位置就不會是答案，因此我們會將 \(right\) 移到 \(mid - 1\) 的位置。

 if(arr[mid] > tar) {
	right = mid - 1;
}

程式碼：

 int l = 0, r = n - 1;
while(l < r) {
	int m = (l + r) / 2;
	if(arr[m] <= tar) {
		l = m;
	}
	else{
		r = m - 1;
	}
}
if(arr[l] == tar) {
	return 1;//有找到，在 l 的位置
}
return -1;//陣列沒有 tar 這個值

複雜度：

由於每次將區間切半，所以複雜度是 \(O(\log_2n)\)

二分搜的條件：

如果將已排序的陣列的 \(index\) 跟值進行映射 (\(x \rightarrow y\))，陣列就會變成單調遞增函數，二分搜就是在單調遞增的函數上進行搜尋。

例題：APCS 基地台

很常見的二分搜例題
題意：在數線上給定 \(n\) 個點，你可以在上面放 \(k\) 個基地台，每個基地台可以服務左右 \(\frac d 2\) 的範圍，詢問你 \(d\) 最少需要多少？ \(n, k, d\) 都是整數

先不管 \(k\) 的限制，可以觀察到 \(d\) 越小我們需要就需要越多的基地台，也就是 \(k\) 跟 \(d\) 成負相關，可以利用這個單調性來計算答案。

可以發現沒辦法直觀的利用 \(k\) 來找到 \(d\)，但如果有 \(d\) 時，計算 \(k\) 會相對簡單。

假設有五個點 \([1, 2, 5, 7, 8]\)， \(d\) 等於 \(5\) 時，要覆蓋到第一個點 \((1)\)，基地台最遠可以放到 \(3\) 的位置，而這個基地台最遠可以覆蓋到 \(5\) 的位置，因此沒被覆蓋到的點只剩 \(7、8\)，我們在剛好只能覆蓋到 \(7\) 的位置 \(9\) 放下基地台，基地台就可以覆蓋全部的點了！

範例程式碼：

 int now = -1, d = 5, k = 0;
for(int i = 0; i < n; i++) {
	if(arr[i] > now) {
		k++;
		now = arr[i] + d;
	}
}
cout << k;

通過上面的程式碼，我們這樣可以花 \(O(n)\) 的時間找到 \(k\)，因此我們可以對 \(d\) 二分搜，找出最小的 \(d\) 會讓基地台的數量大於等於 \(k\)。

當搜出的數字比 \(k\) 小時，我們就需要將右界向左縮，因為 \(d\) 更大只會讓基地台的數量變少，相反的則是左界向右縮，只需要將二分搜跟上面的用 \(d\) 去尋找 \(k\) 的放在一起，就可以解出這題了。

 int check(int d){
    int now = -1, ans = 0;
    for(int i = 0; i < n; i++) {
        if(arr[i] > now) {
            now = arr[i] +  d;
            ans++;
        }
    }
    return ans;
}
signed main(){
    /*....*/
    while(l < r) {
        int mid = (l + r ) / 2;
        int ret = check(mid);
        if(ret <= k) r = mid;
        else         l = mid + 1;
    }
    /*....*/
}

細節：

在二分搜之前要確認搜的東西是有單調性 (遞增、遞減)

細節：

確定答案有在左界跟右界內，沒有的話就只是白做工。

細節：

可以發現根據題目的不同，左界跟右界的縮法會不太一樣

l = m, r = m - 1;
l = m + 1, r = m;
l = m + 1, r = m - 1;

二分搜的重點就是看出題目的性質，決定要怎麼去搜。

注意二分搜並不能只使用單種習慣的方法，需要使用題目的性質來變化你縮的方法。

細節：

承接上頁，決定縮法之後，還要決定 mid 要怎麼求，當縮到最小的時候，有可能因為左右界縮法的問題，就陷入無限迴圈。
當 l=3, r=4, mid=(l+r)/2, l=m, r=m-1 時
如果二分搜的結果是縮左界的話 l \(\rightarrow\) mid，3 \(\rightarrow\)(3+4)/2=3，就會進入無限迴圈了！
這裡的解法是將 mid=(l+r+1)/2，也就是從向下取整改成向上取整。

	while(l < r) {
	int ml = l + (r - l) / 3;
	int mr = r - (r - l) / 3;
	if (check(ml) < check(mr)) {
	r = mr;
	}
	else {
	l = ml;
	}
	}

	struct node{
	double x, y;
	}arr[n];

	double check(double val) {
	double cmax = 0;
	for(int i = 0; i < n; i++) {
	cmax = max(cmax,(arr[i].x - 0) * (arr[i].x - 0) +
	(arr[i].y - val) * (arr[i].y - val));
	}
	return cmax;
	}

	while(r - l > eps) {
	double ml = l + (r - l) / 3;
	double mr = r - (r - l) / 3;
	if (check(ml) < check(mr)) {
	r = mr;
	}
	else {
	l = ml;
	}
	}

	int l = 0, r = n - 1;
	while(l < r) {
	int m = (l + r) / 2;
	if(arr[m] <= tar) {
	l = m;
	}
	else{
	r = m - 1;
	}
	}
	if(arr[l] == tar) {
	return 1;//有找到，在 l 的位置
	}
	return -1;//陣列沒有 tar 這個值

	int now = -1, d = 5, k = 0;
	for(int i = 0; i < n; i++) {
	if(arr[i] > now) {
	k++;
	now = arr[i] + d;
	}
	}
	cout << k;

	int check(int d){
	int now = -1, ans = 0;
	for(int i = 0; i < n; i++) {
	if(arr[i] > now) {
	now = arr[i] + d;
	ans++;
	}
	}
	return ans;
	}
	signed main(){
	/..../
	while(l < r) {
	int mid = (l + r ) / 2;
	int ret = check(mid);
	if(ret <= k) r = mid;
	else l = mid + 1;
	}
	/..../
	}

search algorithm & 實作misc