Хоёртын хайлт¶

Хоёртын хайлт гэдэг нь хайлтын интервалыг хоёр хуваах замаар ямар нэг зүйлийг хурдан хайх боломж олгодог арга юм. Түүний хамгийн түгээмэл хэрэглээ нь эрэмбэлэгдсэн массив дахь утгыг хайх явдал боловч хуваах санаа нь бусад олон ердийн бодлогод чухал үүрэгтэй.

Эрэмбэлэгдсэн массив дахь хайлт¶

Хоёртын хайлтад хүргэдэг хамгийн ердийн бодлого дараах байдалтай. Танд $A_0 \leq A_1 \leq \dots \leq A_{n-1}$ эрэмбэлэгдсэн массив өгөгдсөн, $k$ дараалалд байгаа эсэхийг шалга. Хамгийн энгийн шийдэл бол элемент бүрийг нэг нэгээр нь шалгаж $k$-тай харьцуулах явдал юм (шугаман хайлт гэж нэрлэгддэг). Энэ арга $O(n)$-д ажилладаг боловч массив эрэмбэлэгдсэн гэсэн баримтыг ашиглахгүй.

Массив дахь $7$ утгыг хоёртын хайлтаар хайх нь.
AlwaysAngry-ийн зургийг CC BY-SA 4.0 лицензээр тараасан.

Одоо бид $A_L \leq k \leq A_R$ байх $L < R$ гэсэн хоёр индексийг мэддэг гэж үзье. Массив эрэмбэлэгдсэн тул $k$ нь $A_L, A_{L+1}, \dots, A_R$-ийн дунд орших, эсвэл массивт огт байхгүй гэж дүгнэж болно. Хэрэв бид $L < M < R$ байх дурын $M$ индекс сонгож, $k$ нь $A_M$-ээс бага эсвэл их эсэхийг шалгавал. Бидэнд хоёр боломжит тохиолдол бий:

$A_L \leq k \leq A_M$. Энэ тохиолдолд бид бодлогыг $[L, R]$-ээс $[L, M]$ болгон багасгана;
$A_M \leq k \leq A_R$. Энэ тохиолдолд бид бодлогыг $[L, R]$-ээс $[M, R]$ болгон багасгана.

$M$-ийг сонгох боломжгүй үед буюу $R = L + 1$ үед бид $k$-г $A_L$ ба $A_R$-тай шууд харьцуулна. Эс бөгөөс бид хамгийн муу тохиолдолд идэвхтэй хэрчмийг аль болох хурдан нэг элемент болгон багасгахаар $M$-ийг сонгохыг хүснэ.

Хамгийн муу тохиолдолд бид $[L, M]$ ба $[M, R]$-ийн том хэрчим рүү үргэлж багасгана. Тиймээс хамгийн муу тохиолдолд бууралт нь $R-L$-ээс $\max(M-L, R-M)$ хүртэл байна. Энэ утгыг хамгийн бага болгохын тулд бид $M \approx \frac{L+R}{2}$-г сонгох ёстой, тэгвэл

$$ M-L \approx \frac{R-L}{2} \approx R-M. $$

Өөрөөр хэлбэл хамгийн муу тохиолдлын үүднээс $M$-г үргэлж $[L, R]$-ийн голд сонгож хагаслах нь оновчтой. Тиймээс идэвхтэй хэрчим алхам бүрд хагасалж, $1$ хэмжээтэй болтол багасна. Тэгэхээр процесс $h$ алхам шаардвал эцэст нь $R$ ба $L$-ийн ялгааг $R-L$-ээс $\frac{R-L}{2^h} \approx 1$ болгон багасгаж, бидэнд $2^h \approx R-L$ тэгшитгэлийг өгнө.

Хоёр талд $\log_2$ авбал бид $h \approx \log_2(R-L) \in O(\log n)$-г олж авна.

Логарифм тооны алхам нь шугаман хайлтынхаас эрс дээр. Жишээ нь $n \approx 2^{20} \approx 10^6$-ийн хувьд шугаман хайлтад ойролцоогоор сая үйлдэл хийх шаардлагатай бол хоёртын хайлтаар ердөө $20$ орчим үйлдэл хийнэ.

Lower bound ба upper bound¶

Элементийн яг байрлалыг олохоос илүү $k$-аас их буюу тэнцүү эхний элементийн байрлал (массив дахь $k$-ийн lower bound гэж нэрлэдэг), эсвэл $k$-аас их эхний элементийн байрлал ($k$-ийн upper bound гэж нэрлэдэг)-ыг олох нь ихэвчлэн тохиромжтой байдаг.

Lower ба upper bound хоёр хамтдаа $k$-тай тэнцүү массивын элементүүдийн боломжит хоосон хагас интервалыг үүсгэнэ. $k$ массивт байгаа эсэхийг шалгахын тулд түүний lower bound-ыг олж, харгалзах элемент $k$-тай тэнцэх эсэхийг шалгахад хангалттай.

Implementation¶

The explanation above provides a rough description of the algorithm. For the implementation details, we'd need to be more precise.

We will maintain a pair $L < R$ such that $A_L \leq k < A_R$. Meaning that the active search interval is $[L, R)$. We use half-interval here instead of a segment $[L, R]$ as it turns out to require less corner case work.

When $R = L+1$, we can deduce from definitions above that $R$ is the upper bound of $k$. It is convenient to initialize $R$ with past-the-end index, that is $R=n$ and $L$ with before-the-beginning index, that is $L=-1$. It is fine as long as we never evaluate $A_L$ and $A_R$ in our algorithm directly, formally treating it as $A_L = -\infty$ and $A_R = +\infty$.

Finally, to be specific about the value of $M$ we pick, we will stick with $M = \lfloor \frac{L+R}{2} \rfloor$.

Then the implementation could look like this:

... // a sorted array is stored as a[0], a[1], ..., a[n-1]
int l = -1, r = n;
while (r - l > 1) {
    int m = (l + r) / 2;
    if (k < a[m]) {
        r = m; // a[l] <= k < a[m] <= a[r]
    } else {
        l = m; // a[l] <= a[m] <= k < a[r]
    }
}

During the execution of the algorithm, we never evaluate neither $A_L$ nor $A_R$, as $L < M < R$. In the end, $L$ will be the index of the last element that is not greater than $k$ (or $-1$ if there is no such element) and $R$ will be the index of the first element larger than $k$ (or $n$ if there is no such element).

Note. Calculating m as m = (r + l) / 2 can lead to overflow if l and r are two positive integers, and this error lived about 9 years in JDK as described in the blogpost. Some alternative approaches include e.g. writing m = l + (r - l) / 2 which always works for positive integer l and r, but might still overflow if l is a negative number. If you use C++20, it offers an alternative solution in the form of m = std::midpoint(l, r) which always works correctly.

Дурын предикат дээрх хайлт¶

$f : \{0,1,\dots, n-1\} \to \{0, 1\}$ нь $0,1,\dots,n-1$ дээр тодорхойлогдсон монотон өсөх булев функц байг, өөрөөр хэлбэл

$$ f(0) \leq f(1) \leq \dots \leq f(n-1). $$

Дээр тайлбарласан хоёртын хайлт нь $k < A_M$ илэрхийллийн булев утгыг агуулах $f(M)$ предикатаар массивын хуваалтыг олдог. $k < A_M$-ийн оронд дурын монотон предикат ашиглаж болно. Энэ нь $f(k)$-г тооцоолоход боломжит утга бүрийн хувьд бодитоор тооцоолоход хэт их хугацаа шаардагдах үед онцгой ашигтай. Өөрөөр хэлбэл хоёртын хайлт нь ийм шилжилтийн цэг байвал $f(L) = 0$ ба $f(R)=f(L+1)=1$ байх цор ганц $L$ индексийг олно, эсвэл $f(0) = \dots = f(n-1) = 0$ бол бидэнд $L = n-1$-г, $f(0) = \dots = f(n-1) = 1$ бол $L = -1$-г өгнө.

Шилжилтийн цэг оршин байна, өөрөөр хэлбэл $f(0)=0$ ба $f(n-1)=1$ гэж үзвэл зөв байдлын баталгаа: Хэрэгжүүлэлт нь $f(l)=0, f(r)=1$ гэсэн давталтын инвариант-ыг хадгална. $r - l > 1$ үед $m$-ийн сонголт нь $r-l$-г үргэлж багасгана гэсэн үг. Давталт $r - l = 1$ болоход зогсох ба бидэнд хайж буй шилжилтийн цэгийг өгнө.

... // f(i) is a boolean function such that f(0) <= ... <= f(n-1)
int l = -1, r = n;
while (r - l > 1) {
    int m = (l + r) / 2;
    if (f(m)) {
        r = m; // 0 = f(l) < f(m) = 1
    } else {
        l = m; // 0 = f(m) < f(r) = 1
    }
}

Хариун дээрх хоёртын хайлт¶

Ийм нөхцөл байдал нь бид ямар нэг утга тооцоолохыг шаардагдах боловч зөвхөн энэ утга дор хаяж $i$ эсэхийг шалгаж чадах үед ихэвчлэн тохиолддог. Жишээ нь танд $a_1,\dots,a_n$ массив өгөгдсөн бөгөөд $r-l \geq x$ байх бүх боломжит $l,r$ хосын дундаас хамгийн их доор бүхэлчилсэн дундаж нийлбэр

$$ \left \lfloor \frac{a_l + a_{l+1} + \dots + a_r}{r-l+1} \right\rfloor $$

-г олохыг шаардаж байна. Энэ бодлогыг бодох энгийн аргуудын нэг бол хариу дор хаяж $\lambda$ эсэхийг буюу дараах нь үнэн байх $l, r$ хос байгаа эсэхийг шалгах явдал юм:

$$ \frac{a_l + a_{l+1} + \dots + a_r}{r-l+1} \geq \lambda. $$

Эквивалентаар үүнийг

$$ (a_l - \lambda) + (a_{l+1} - \lambda) + \dots + (a_r - \lambda) \geq 0, $$

гэж бичих ба одоо бид $a_i - \lambda$ шинэ массивын урт нь дор хаяж $x+1$, нийлбэр нь сөрөг биш дэд массив байгаа эсэхийг шалгах хэрэгтэй болно, үүнийг угтвар нийлбэрээр хийж болно.

Тасралтгүй хайлт¶

$f : \mathbb R \to \mathbb R$ нь $[L, R]$ хэрчим дээр тасралтгүй бодит утгат функц байг.

Ерөнхий чанараа алдалгүйгээр $f(L) \leq f(R)$ гэж үзье. Завсрын утгын теорем-оос дурын $y \in [f(L), f(R)]$-ийн хувьд $f(x) = y$ байх $x \in [L, R]$ байх нь гарна. Өмнөх догол мөрүүдээс ялгаатай нь функц монотон байх шаардлагагүй гэдгийг анхаарна уу.

$x$ утгыг дурын тодорхой $\delta$ утгын хувьд $O\left(\log \frac{R-L}{\delta}\right)$ хугацаанд $\pm\delta$ хүртэл нарийвчлалтайгаар ойролцоолж болно. Санаа нь үндсэндээ ижил, хэрэв бид $M \in (L, R)$ авбал $f(M)$ нь $y$-ээс их эсэхээс хамааран хайлтын интервалыг $[L, M]$ эсвэл $[M, R]$ болгон багасгаж чадна. Энд түгээмэл жишээ бол сондгой зэргийн олон гишүүнтийн язгуурыг олох явдал юм.

Жишээ нь $f(x)=x^3 + ax^2 + bx + c$ байг. Тэгвэл $L \to -\infty$ ба $R \to +\infty$ үед $f(L) \to -\infty$ ба $f(R) \to +\infty$ болно. Энэ нь $f(L) < 0$ ба $f(R) > 0$ байх хангалттай бага $L$ ба хангалттай том $R$-г үргэлж олох боломжтой гэсэн үг. Дараа нь хоёртын хайлтаар $f(x)=0$ байх $x$-г агуулсан дурын бага интервалыг олох боломжтой.

2-ын зэргээр хайх¶

Хоёртын хайлт хийх бас нэг анхаарал татахуйц арга бол идэвхтэй хэрчим хадгалахын оронд одоогийн заагч $i$ ба одоогийн зэрэг $k$-г хадгалах явдал юм. Заагч $i=L$-ээс эхэлж, дараа нь итерац бүрд $i+2^k$ цэг дээр предикатыг шалгана. Хэрэв предикат $0$ хэвээр байвал заагч $i$-ээс $i+2^k$ хүртэл ахих, эс бөгөөс хэвээрээ үлдэх ба дараа нь $k$ зэргийг $1$-ээр багасгана.

Энэ парадигмыг хоёр оройн хамгийн бага нийтлэг өвгийг олох буюу тодорхой өндөртэй тухайн оройн өвгийг олох зэрэг модны эргэн тойрны бодлогод өргөнөөр ашигладаг. Үүнийг мөн жишээ нь Фенвикийн мод дахь $k$-р тэг биш элементийг олоход тохируулж болно.