Эрэмбэлэгдсэн array-д x-ээс багагүй хамгийн эхний тооны index-ийг Binary Search ашиглан олдог арга.

Pre-IntermediateХугацаа: O(log n)Санах ой: O(1)
HackerRank дээр бодох

Эхлээд жижиг бодлого

Эрэмбэлэгдсэн a = [1, 3, 3, 5, 8] array-д 3-аас багагүй хамгийн эхний тоо хаана байна вэ? Хариу нь index 1.

Харин 4-ийг асуувал хариу 3 (тэнд 5 байна). 9-ийг асуувал бүх тоо 9-өөс бага тул хариу n = 5.

Энгийн аргаас санаа руу

Энгийн Binary Search тоо байгаа эсэхийг л хэлдэг. Ижил тоо олон байвал аль нэгийг нь олно. Гэтэл олон бодлогод "x хаанаас эхэлдэг вэ?", "x-ээс бага хэдэн тоо байна?" гэж асуудаг.

Lower Bound хүрээг [lo, hi) гэж хадгална. a[mid] >= x бол mid өөрөө хариу байж болох тул хаяхгүй: hi = mid. Үгүй бол mid болон түүнээс зүүн тийш бүх тоо хэт бага: lo = mid + 1. Хүрээ хоосон болоход lo нь хариу.

Нэр томьёо ба тэмдэглэгээ

[lo, hi)
lo хүрээнд орно, hi орохгүй. Эхэндээ lo = 0, hi = n.
mid
Хүрээний дунд: (lo + hi) / 2. lo < hi үед mid нь hi-гаас үргэлж бага тул array-гээс гарахгүй.
lower_bound
C++-ийн бэлэн function. lower_bound(a, a + n, x) - a нь яг энэ кодын хариу.
lo = 0hi = 10

a[i] ≥ 7 байх хамгийн эхний i-г хайна. Эхлээд lo = 0, hi = 10. hi нь array-н яг ард байна.

Алхам 1 / 10
Хурд
  • Энгийн
  • mid
  • Хариу (lo)
  • Хайлтаас хасагдсан
Слайд 1 / 7

Хамгийн эхнийх нь хаана?

Энэ array-д 7 гурван удаа байна. Тэдний хамгийн эхнийх нь хаана вэ? Lower Bound хариуг Binary Search ашиглан хурдан олно.

lower-bound.cpp
#include <bits/stdc++.h>
using namespace std;
int n, x, a[100005];
int main() {
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];
cin >> x;
int lo = 0, hi = n;
while (lo < hi) {
int mid = (lo + hi) / 2;
if (a[mid] >= x) {
hi = mid;
} else {
lo = mid + 1;
}
}
cout << lo << '\n';
return 0;
}

Юунд хэрэгтэй вэ?

"x хаанаас эхэлдэг вэ?", "x-ээс бага тоо хэд байна?" гэх мэт асуултад log n алхамд хариулах. C++-ийн lower_bound яг ингэж ажилладаг.

Яаж ажилладаг вэ?

1. Хайх хүрээ: lo = 0, hi = n (hi өөрөө хүрээнд орохгүй). 2. Дундах index: mid = (lo + hi) / 2. 3. a[mid] ≥ x бол хариу нь mid эсвэл түүнээс зүүн талд: hi = mid. 4. a[mid] < x бол хариу баруун талд: lo = mid + 1. 5. lo = hi болоход lo нь хариу. Ийм тоо байхгүй бол хариу n. Оролт: n, n ширхэг эрэмбэлэгдсэн тоо, дараа нь x.

Яагаад зөв, хэр хурдан бэ?

Loop-ын турш хоёр зүйл үнэн хэвээр байна: lo-гоос зүүн талын бүх тоо x-ээс бага, hi болон түүнээс баруун талын бүх тоо x-ээс багагүй. lo = hi болоход хариу яг тэр зааг дээр байна.

Алхам бүрт хүрээ хоёр дахин багасна. n = 1 000 000 бол 20 орчим алхам: хугацаа O(log n), нэмэлт санах ой O(1).

Түгээмэл алдаа

  • hi = mid - 1 гэж бичвэл mid дээрх хариуг алдана.
  • while (lo <= hi) гэж бичвэл lo = hi үед hi = mid хүрээг багасгахгүй тул loop дуусахгүй.
  • hi = n - 1 гэж эхлүүлбэл бүх тоо x-ээс бага үед n гэсэн хариу гарч чадахгүй.
  • Эрэмбэлэгдээгүй array дээр хэрэглэх. Эхлээд sort(a, a + n) хийнэ.

Хязгаарын тохиолдол

  • Бүх тоо x-ээс бага: хариу n, өөрөөр хэлбэл array-н яг ард.
  • Бүх тоо x-ээс багагүй: хариу 0.
  • x олон удаа байгаа: хамгийн эхнийх нь index.
  • n = 1: нэг алхмаар lo нь 0 эсвэл 1 болно.

Өөрийгөө шалга

  1. a = [2, 4, 4, 7, 7, 7, 9, 12, 15, 20], x = 7. Хариу хэд вэ?

    Хариу харах

    3.

  2. Энэ array-д 7 хэдэн удаа байгааг Lower Bound-ыг хоёр удаа ашиглаж яаж олох вэ?

    Хариу харах

    x = 8 үеийн хариунаас x = 7 үеийн хариуг хасна: 6 − 3 = 3.

  3. n = 1 000 000 бол loop хэдэн удаа ажиллах вэ?

    Хариу харах

    20 орчим. 2²⁰ ≈ 1 000 000.

Гурван дадлага

Hint-ээ нээхээс өмнө өөрөө оролдоорой.

  1. 1.a = [1, 2, 2, 2, 5, 6], x = 2 үед lo, hi, mid ямар утга авахыг алхам алхмаар бич.

    Hint харах

    Эхлээд lo = 0, hi = 6.

    Хариу ба тайлбар

    mid = 3: 2 ≥ 2, hi = 3. mid = 1: 2 ≥ 2, hi = 1. mid = 0: 1 < 2, lo = 1. Хариу 1.

  2. 2.x-ээс их хамгийн эхний тооны index-ийг ол (Upper Bound).

    Hint харах

    Ганц тэмдэгт өөрчлөхөд хангалттай.

    Хариу ба тайлбар

    if (a[mid] > x) болгоно. C++-д энэ нь upper_bound.

  3. 3.Q асуулт ирнэ: тус бүрд [L, R] хооронд хэдэн тоо байгааг ол (n, Q ≤ 10⁵).

    Hint харах

    Array-г эрэмбэлээд хоёр Lower Bound-ын зөрүүг ав.

    Хариу ба тайлбар

    Хариу нь lower_bound(R + 1) - lower_bound(L). Асуулт бүр O(log n).

Жишээ

Оролт

10
2 4 4 7 7 7 9 12 15 20
7

Гаралт

3

Одоо өөрөө бодоод үз

Бодлого

Хичээл

Энэ сэдвийн хичээл удахгүй нэмэгдэнэ.