開啟章節選單
對答案二分搜
常見使用時機
如果題目給的是可以套進某個函式的資料,並且這些資料具有單調性,那麼我們就可以使用對答案二分搜這個技巧來解題。
舉例
給定一函式 ,我們可以觀察到 是具有單調性的,他符合嚴格遞增的條件,此時如果要搜尋第一個小於 的 ,我們可以透過以下程式碼求得答案。
bool check(int x) { if (x! < 130) { // 省略了求階乘的過程 return true; } else { return false; } } int binary_search() { // 範例是使用半開半閉的二分搜,也可以使用別的二分搜實作 int left = 1, right = n, ans; while (left + 1 < right) { int mid = (left + right) / 2; if (check(mid) == true) { left = mid; } else { right = mid; } } ans = left; }