Chiziqli qidiruv
Chiziqli qidiruv qanday ishlaydi va uning vaqt murakkabligi
Kirish
ta sondan iborat massiv berilgan. Biz sonining indeksini topishimiz kerak. Ya'ni, shunday topilsinki, bo'lsin. Yoki, bunday indeks mavjud emasligini aytish kerak.
Chiziqli qidiruv qanday ishlaydi va uning vaqt murakkabligi
ta sondan iborat massiv berilgan. Biz sonining indeksini topishimiz kerak. Ya'ni, shunday topilsinki, bo'lsin. Yoki, bunday indeks mavjud emasligini aytish kerak.
Bu masalani yechish uchun chiziqli qidiruvdan foydalanish mumkin. Chiziqli qidiruv - bu massiv bo'ylab boshidan oxirigacha yurib, har bir elementni tekshiradigan va kerakli elementni topguncha davom etadigan algoritm. Bu algoritmning vaqt murakkabligi , chunki eng yomon holatda u barcha sonlarni tekshirishi mumkin.
Implementatsiya uchun ham for siklidan, ham while siklidan foydalanish mumkin.
int Search(const vector<int>& a, int x) {
for (size_t i = 0; i < a.size(); i++) {
if (a[i] == x) {
return i;
}
}
return -1; // agar mavjud bo'lmasa
}
int Search(const vector<int>& a, int x) {
size_t i = 0;
while (i < a.size() && a[i] != x) {
i += 1;
}
if (i == a.size()) {
return -1;
}
return i;
}