Эрэмбэлэгдсэн array-н дундах утгыг шалгаж, хайх хүрээгээ алхам бүрт хоёр дахин багасгадаг хурдан хайлт.

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

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

Эрэмбэлэгдсэн a = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91] array-гээс 23-ыг хайя. Хариу нь index 5.

Эхнээс нь нэг нэгээр нь шалгавал 6 харьцуулалт хийнэ. Binary Search ердөө 3 удаа mid-ийг шалгаад олно.

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

Хамгийн энгийн арга бол эхнээс нь нэг нэгээр харах. n = 1 000 000 бол хамгийн муудаа сая удаа шалгана.

Гэтэл array эрэмбэлэгдсэн байгаа. Дунд байгаа a[mid]-ийг харахад л хариу аль талд байгааг мэднэ: a[mid] < x бол x зүүн хагаст байж чадахгүй тул тэр хагасыг бүхэлд нь хаяна. Алхам бүрт хайх хүрээ хоёр дахин багасна.

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

lo, hi
Хариу байж болох хүрээний зүүн ба баруун зааг. Хоёулаа хүрээнд багтана.
mid
Хүрээний дунд index: (lo + hi) / 2.
эрэмбэлэгдсэн array
Утгууд нь багаас их рүү дараалсан array. Binary Search зөвхөн үүн дээр ажиллана.
-1
Хайсан тоо array-д байхгүй гэдгийг илэрхийлэх хариу.

23-ыг хайна. Эхлээд бүх array дотроос хайна: lo = 0, hi = 9.

Алхам 1 / 8
Хурд
  • Энгийн
  • mid
  • Олдсон
  • Хайлтаас хасагдсан
Слайд 1 / 5

Тоо таах тоглоом

Найз чинь 1-ээс 100 хүртэлх нэг тоо бодсон гэж бод. "50 үү, их үү, бага уу?" гэж дундаас нь асуусаар байвал 7 асуултаар олно. Binary Search яг ингэж хайдаг.

binary-search.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 - 1, ans = -1;
while (lo <= hi) {
int mid = (lo + hi) / 2;
if (a[mid] == x) {
ans = mid;
break;
} else if (a[mid] < x) {
lo = mid + 1;
} else {
hi = mid - 1;
}
}
cout << ans << '\n';
return 0;
}

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

Эрэмбэлэгдсэн их өгөгдлөөс тоог маш хурдан олох: сая тоон дотроос 20 орчим шалгалтаар олно.

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

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

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

Алхам бүрт хаясан хагаст x байх боломжгүй: a[mid] < x бол mid болон түүнээс зүүн талын бүх утга x-ээс бага. Тиймээс x array-д байгаа бол үргэлж [lo, hi] дотор үлдэнэ.

Хүрээ n, n/2, n/4 гэж багасаад нэг элемент болоход log₂ n орчим алхам хийнэ. Сая элементтэй array-д 20 хүрэхгүй удаа шалгана: хугацаа O(log n), нэмэлт санах ой O(1).

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

  • Эрэмбэлэгдээгүй array дээр хэрэглэх. Эхлээд sort(a, a + n) хийх ёстой.
  • lo = mid эсвэл hi = mid гэж бичвэл хүрээ багасахгүй, loop дуусахгүй. mid + 1, mid - 1 гэж бич.
  • while (lo < hi) гэж бичвэл сүүлийн нэг элементийг шалгалгүй алгасна. Энэ кодод lo <= hi хэрэгтэй.
  • Маш том index дээр lo + hi нь int-ээс хэтэрч болно. lo + (hi - lo) / 2 гэж бичвэл аюулгүй.

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

  • Хайсан тоо байхгүй: lo > hi болоход loop дуусч -1 хэвлэнэ.
  • Array-д ганц элемент: нэг л шалгалтаар шийдэгдэнэ.
  • Хайсан тоо хамгийн эхэнд эсвэл төгсгөлд: хүрээ нэг тал руугаа шахагдаж олно.
  • Ижил утга олон: энэ код аль нэгийг нь олно, заавал эхнийхийг биш. Эхнийх нь хэрэгтэй бол Lower Bound-ыг үз.

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

  1. a = [1, 3, 5, 7, 9, 11, 13] дотроос 13-ыг хайхад mid хэдэн удаа шалгагдах вэ?

    Хариу харах

    3 удаа: mid = 3 (7), mid = 5 (11), mid = 6 (13).

  2. 1 000 000 элементтэй array-д хамгийн муудаа хэдэн удаа шалгах вэ?

    Хариу харах

    20 орчим. 2²⁰ ≈ 1 000 000 тул хүрээг 20 удаа хуваахад нэг элемент үлдэнэ.

  3. Яагаад эрэмбэлэгдээгүй array дээр ажиллахгүй вэ?

    Хариу харах

    a[mid] < x үед x зүүн талд байхгүй гэж хэлэх эрх зөвхөн эрэмбэлэгдсэн үед л бий. Эрэмбэгүй бол хаясан хагаст x байж болно.

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

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

  1. 1.a = [4, 9, 15, 21, 30] дотроос 21-ийг хайхад lo, hi, mid ямар утга авахыг алхам алхмаар бич.

    Hint харах

    Эхлээд lo = 0, hi = 4, mid = 2.

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

    mid = 2: 15 < 21 тул lo = 3. mid = 3: 21 олдлоо. Хариу 3.

  2. 2.Тоо олдохгүй бол -1-ийн оронд тэр тоог хаана оруулбал array эрэмбэлэгдсэн хэвээр үлдэхийг хэвлэдэг болго.

    Hint харах

    Loop дуусахад lo хаана зогсож байгааг ажигла.

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

    Loop дуусахад lo нь x-ээс их хамгийн эхний элементийн index байна. Тиймээс -1-ийн оронд lo-г хэвлэнэ.

  3. 3.Ижил утга олон байж болох үед x-ээс бага биш хамгийн эхний элементийн index-ийг ол.

    Hint харах

    a[mid] >= x үед mid өөрөө хариу байж болно. Хадгалаад зүүн тийш үргэлжлүүлэн хай.

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

    if (a[mid] >= x) { ans = mid; hi = mid - 1; } else lo = mid + 1; Эцэст нь ans хариу болно. Үүнийг Lower Bound гэдэг.

Жишээ

Оролт

10
2 5 8 12 16 23 38 56 72 91
23

Гаралт

5

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

Бодлого

Хичээл

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