Уул хэлбэртэй array-н оргилыг хэсгийг гуравт хувааж олдог хайлт.

IntermediateХугацаа: O(log n)Санах ой: O(1)

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

a = [12, 25, 39, 54, 70, 61, 47, 38, 26, 15, 4] эхлээд өсөөд, дараа нь буурдаг. Оргил нь хаана вэ?

Хамгийн өндөр нь index 4 дээрх 70. Хариу: 4 70.

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

Энгийн арга: бүх тоог шалгаад хамгийн их нь. O(n). Тоонууд function-аар өгөгдөж, нэг утгыг бодох нь удаан бол энэ хэтэрхий олон алхам.

Гол санаа: хоёр цэг m1 < m2 сонгоод a[m1], a[m2] хоёрыг харьцуулна. a[m1] < a[m2] бол m1 өгсөх талд байна, оргил m1-ээс баруун талд. Тиймээс [l, m1] хэсгийг хаяна. Эсрэгээрээ бол [m2, r] хэсгийг хаяна. Алхам бүрт хэсгийн гуравны нэг орчим нь хаягдана.

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

l, r
Оргил байж болох хэсгийн зааг.
m1, m2
Хэсгийг гуравт хуваах цэгүүд: l + (r - l) / 3, r - (r - l) / 3.
уул хэлбэртэй
Хатуу өсөөд хатуу буурдаг дараалал. Хажуу хоёр тоо тэнцүү байж болохгүй.
best
Сүүлд үлдсэн хэдэн тооноос хамгийн өндрийнх нь index.
l = 0r = 10

Тоонууд эхлээд өсөөд, дараа нь буурдаг. Яг уул шиг. Оргилыг нь олъё. Бүгдийг шалгахгүй: хэсгийг гуравт хувааж, нэг хэсгийг нь хаяна.

Алхам 1 / 9
Хурд
  • Энгийн
  • a[m1] ба a[m2]
  • Одоогийн хамгийн өндөр
  • Оргил
  • Хаягдсан хэсэг
Слайд 1 / 6

Уулын оргил

Тоонууд өсөөд, дараа нь буурдаг. Яг уул шиг. Хамгийн өндөр цэгийг олъё. Энэ array эрэмбэлэгдээгүй тул Binary Search шууд ажиллахгүй.

ternary-search.cpp
#include <bits/stdc++.h>
using namespace std;
int n, a[100005];
int main() {
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];
int l = 0, r = n - 1;
while (r - l > 2) {
int m1 = l + (r - l) / 3, m2 = r - (r - l) / 3;
if (a[m1] < a[m2]) {
l = m1 + 1;
} else {
r = m2 - 1;
}
}
int best = l;
for (int i = l + 1; i <= r; i++) {
if (a[i] > a[best]) {
best = i;
}
}
cout << best << ' ' << a[best] << '\n';
return 0;
}

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

Эхлээд өсөөд, дараа нь буурдаг дарааллын хамгийн их утгыг log алхамд олно. Буураад өсдөг бол хамгийн бага утгыг яг ийм аргаар олно.

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

1. [l, r] хэсгийг m1 = l + (r − l) / 3, m2 = r − (r − l) / 3 цэгүүдээр гуравт хуваана. 2. a[m1] < a[m2] бол өгсөж байна: оргил m1-ээс баруун талд байна, l = m1 + 1. 3. Үгүй бол уруудаж байна: оргил m2-оос зүүн талд байна, r = m2 − 1. 4. 3 тоо үлдэхэд нэг нэгээр нь шалгана. Хажуу хоёр тоо тэнцүү байж болохгүй. Тэгвэл буруу хэсгийг хаяж магадгүй. Оролт: n, дараа нь n тоо. Гаралт: оргилын index ба утга.

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

a[m1] < a[m2] бол m1 оргилоос зүүн талд байх ёстой. m1 буурах талд байсан бол m2 түүнээс ч доор байх байсан. Тиймээс оргил хаягдсан хэсэгт хэзээ ч байхгүй. Эсрэг тохиолдол нь мөн адил.

Алхам бүрт хэсгийн урт ойролцоогоор 2/3 дахин багасна. n = 10⁶ бол 35 орчим алхам. Хугацаа O(log n), санах ой O(1).

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

  • Хажуу хоёр тоо тэнцүү байвал (хавтгай хэсэгтэй бол) арга буруу хэсгийг хаяж болно.
  • Бодит тоон (double) дээр ажиллахдаа while (r - l > 2) биш, тодорхой тооны давталт хийнэ. Жишээ нь 100 удаа.
  • Буурч байгаад өсдөг (хонхор) дараалал дээр харьцуулалтыг эргүүлэхээ мартах. Хамгийн бага утга хайхад a[m1] > a[m2] бол зүүнийг хаяна.

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

  • Зөвхөн өсдөг array: оргил нь сүүлийн тоо. a[m1] < a[m2] үргэлж үнэн тул зүүн тал хаягдсаар байна.
  • Зөвхөн буурдаг array: оргил нь эхний тоо.
  • n ≤ 3: loop огт эргэхгүй, бүгдийг нэг нэгээр нь шалгана.

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

  1. l = 0, r = 10 бол m1, m2 хэд вэ?

    Хариу харах

    m1 = 3, m2 = 7.

  2. a[m1] > a[m2] бол аль хэсгийг хаях вэ?

    Хариу харах

    Баруун хэсгийг: r = m2 − 1. Оргил m2-оос зүүн талд байна.

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

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

  1. 1.a = [1, 4, 9, 16, 12, 7, 3] дээр m1, m2 ба хаясан хэсгийг алхам алхмаар бич.

    Hint харах

    Эхлээд l = 0, r = 6 тул m1 = 2, m2 = 4.

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

    m1 = 2, m2 = 4: 9 < 12 тул l = 3. m1 = 4, m2 = 5: 12 > 7 тул r = 4. Үлдсэн 16, 12 хоёроос 16 өндөр. Хариу: 3 16.

  2. 2.Кодыг хонхор (эхлээд буурч, дараа нь өсдөг) array-н хамгийн бага утгыг олдог болго.

    Hint харах

    Хоёр харьцуулалтыг л эргүүлнэ.

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

    if (a[m1] > a[m2]) l = m1 + 1; else r = m2 - 1; гэж бичээд, сүүлийн шалгалтыг a[i] < a[best] болгоно.

  3. 3.f(x) = (x − 3)² + 1 функцийн хамгийн бага утгыг [0, 10] дээр бодит x-ээр ол.

    Hint харах

    Index биш бодит тоон дээр m1, m2-ыг бодоод 100 удаа давт.

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

    m1 = l + (r − l) / 3, m2 = r − (r − l) / 3. f(m1) > f(m2) бол l = m1, үгүй бол r = m2. 100 давталтын дараа x ≈ 3, хамгийн бага утга нь 1.

Жишээ

Оролт

11
12 25 39 54 70 61 47 38 26 15 4

Гаралт

4 70