Array-н тоонуудыг эхнээс нь нэг нэгээр шалгаж, хайж буй тоог олдог хамгийн энгийн хайлт.

Basic LevelХугацаа: O(n)Санах ой: O(1)
HackerRank дээр бодох

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

a = [7, 3, 9, 3] array-гээс 9-ийг хайя. a[0] = 7 биш, a[1] = 3 биш, a[2] = 9. Олдлоо! Хариу нь index 2.

Хэрэв 5-ыг хайсан бол дөрвүүлэнг нь шалгаад олдохгүй тул -1 хэвлэнэ.

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

Array эрэмбэлэгдээгүй бол хайж буй тоо хаана ч байж болно. Тэгэхээр тоо бүрийг нэг нэгээр нь харахаас өөр арга алга.

Эхнээс нь эхлэн a[i] == x эсэхийг шалгана. Таарвал ans = i болгоод break хийнэ. Ингэснээр хамгийн эхний тохиолдол олдоно. Loop дуустал олдохгүй бол ans = -1 хэвээр үлдэнэ.

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

ans
Хариу. Эхэндээ -1, олдвол тухайн index.
break
Loop-ыг шууд зогсооно. Олсны дараа цааш шалгахгүй.
-1
Тоо байхгүй гэсэн тэмдэг. Index хэзээ ч сөрөг байдаггүй тул андуурахгүй.

20-ийг хайна. Эхнээс нь нэг нэгээр шалгая.

Алхам 1 / 10
Хурд
  • Энгийн
  • Шалгаж буй
  • Олдсон
Слайд 1 / 5

Нэг нэгээр нь шалгана

Шүүгээнээсээ оймсоо хайхдаа нэг нэгээр нь харж шалгадаг. Linear Search ч тоо бүрийг эхнээс нь дараалан шалгана.

linear-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 ans = -1;
for (int i = 0; i < n; i++) {
if (a[i] == x) {
ans = i;
break;
}
}
cout << ans << '\n';
return 0;
}

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

Эрэмбэлэгдээгүй array-гээс тоо хайх. Олдвол хамгийн эхний index-ийг нь, олдохгүй бол -1 хэвлэнэ.

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

1. i = 0, 1, …, n − 1 гэж тоо бүрийг харна. 2. a[i] = x бол олдлоо: ans = i болгоод break хийнэ. 3. Эцэст нь ans утгыг хэвлэнэ. Олдоогүй бол ans = -1 хэвээрээ. Оролт: n, n ширхэг тоо, дараа нь хайх тоо x.

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

Тоо бүрийг дарааллаар нь шалгадаг тул x байгаа бол заавал олно. Эхний таарсан дээр break хийдэг тул хамгийн бага index-ийг өгнө.

Хамгийн муудаа n шалгалт: хугацаа O(n), нэмэлт санах ой O(1). n = 100 000 бол нэг хайлт маш хурдан. Харин 100 000 асуулт тус бүрд нь хайвал 10¹⁰ алхам болно. Ийм үед эрэмбэлээд Binary Search ашигла.

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

  • break мартвал хамгийн сүүлийн тохиолдлын index гарна.
  • int ans = 0; гэж эхлүүлбэл олдоогүй үед 0 хэвлэгдэж, "index 0-д байна" гэсэн буруу хариу болно.
  • Олон асуулттай бодлогод асуулт бүрт Linear Search хийх. n ба асуултын тоо хоёулаа 10⁵ бол хугацаа хэтэрнэ.
  • Оролтын дарааллыг андуурах. Энэ бодлогод эхлээд n, дараа нь тоонууд, хамгийн сүүлд x ирнэ.

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

  • x байхгүй: n шалгалт хийгээд -1.
  • x хэд хэдэн удаа байгаа: хамгийн эхнийх нь index.
  • x хамгийн эхэнд: ганц шалгалтаар олно.
  • n = 1: ганц тоог шалгана.

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

  1. Анхдагч жишээ [10, 50, 30, 70, 80, 60, 20, 90, 40] дээр 20-ийг хайхад хэдэн тоо шалгах вэ?

    Хариу харах

    7. 20 нь index 6-д байгаа тул a[0]-ээс a[6] хүртэл шалгана.

  2. Яагаад x-ийг олмогц шууд break хийдэг вэ?

    Хариу харах

    Хамгийн эхний тохиолдол л хэрэгтэй. Цааш шалгах нь дэмий ажил.

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

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

  1. 1.a = [4, 8, 4, 1], x = 4 бол хариу хэд вэ? x = 5 бол?

    Hint харах

    Хамгийн эхний тохиолдлыг хайна.

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

    x = 4 бол 0. x = 5 бол -1.

  2. 2.x хэдэн удаа байгааг тоолдог болго.

    Hint харах

    Олсны дараа зогсох хэрэгтэй юу?

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

    break-ийг арилгаад, таарах бүрт cnt++ хийнэ. Эцэст нь cnt утгыг хэвлэнэ.

  3. 3.Хамгийн сүүлийн тохиолдлын index-ийг ол.

    Hint харах

    Array-г ямар чиглэлд гүйлгэвэл эхний олдсон нь хамгийн сүүлийнх болох вэ?

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

    for (int i = n - 1; i >= 0; i--) гэж ар талаас нь гүйлгэнэ. Үлдсэн код хэвээр.

Жишээ

Оролт

9
10 50 30 70 80 60 20 90 40
20

Гаралт

6

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

Бодлого

Хичээл

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