2-dars: Massivda qidiruv (Linear va Binary Search)
Dars haqida
Davomiyligi: 90 daqiqa Maqsad: Talaba linear va binary search algoritmlarini bilishi, ularning farqini va Big O notatsiyasini tushunishi kerak.
1. Qidiruv muammosi
Massivda qidirilayotgan elementni topish.
Massiv: [3, 7, 1, 9, 4, 6, 2, 8, 5]
Target: 6
Natija: Index 5 (yoki "topilmadi")2. Linear Search
Eng oddiy — har element bilan tekshirish.
int linear_search(int arr[], int n, int target) {
for (int i = 0; i < n; i++) {
if (arr[i] == target) {
return i; // topildi
}
}
return -1; // topilmadi
}Misol
int arr[] = {3, 7, 1, 9, 4, 6, 2, 8, 5};
int n = 9;
int index = linear_search(arr, n, 6);
if (index != -1) {
printf("Topildi: index %d\n", index);
} else {
printf("Topilmadi\n");
}3. Linear Search tezligi
| Holat | Tekshirishlar |
|---|---|
| Eng yaxshi | 1 (birinchi element) |
| O'rtacha | n/2 |
| Eng yomon | n (oxirgi yoki yo'q) |
Big O: O(n) — chiziqli.
1000 element — 1000 tekshirish (eng yomonida).
4. Binary Search
Shartlar: massiv sortlangan bo'lishi kerak.
G'oya: har iteratsiyada — yarmini tashlash.
Kod
int binary_search(int arr[], int n, int target) {
int left = 0;
int right = n - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}Misol
int arr[] = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
int n = 10;
int index = binary_search(arr, n, 11);
// Topildi: index 55. Binary Search tezligi
| n | Linear | Binary |
|---|---|---|
| 10 | 10 | 4 |
| 100 | 100 | 7 |
| 1,000 | 1,000 | 10 |
| 1,000,000 | 1,000,000 | 20 |
| 1,000,000,000 | 1,000,000,000 | 30 |
Big O: O(log n) — logarithmic.
Tezlik farqi
1 milliard element:
- Linear: ~1 milliard amaliyot (sekundlar)
- Binary: 30 amaliyot (millisekund)
33 million baravar tezroq!
6. Binary Search qadamma-qadam
arr = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19], target = 11
Iter 1: left=0, right=9, mid=4
arr[4] = 9, target = 11
9 < 11 → left = 5
Iter 2: left=5, right=9, mid=7
arr[7] = 15, target = 11
15 > 11 → right = 6
Iter 3: left=5, right=6, mid=5
arr[5] = 11, target = 11
TOPILDI! Return 57. Rekursiv Binary Search
int binary_search_rec(int arr[], int left, int right, int target) {
if (left > right) return -1;
int mid = (left + right) / 2;
if (arr[mid] == target) return mid;
if (arr[mid] < target) {
return binary_search_rec(arr, mid + 1, right, target);
} else {
return binary_search_rec(arr, left, mid - 1, target);
}
}8. Linear vs Binary — qachon?
| Holat | Qaysi |
|---|---|
| Massiv sortlanmagan | Linear |
| Massiv sortlangan | Binary (tezroq) |
| Kichik massiv (< 100) | Farqi yo'q |
| Katta massiv (> 1000) | Binary |
| Bir martalik qidiruv | Linear (sortlash kerakmas) |
| Ko'p marta qidiruv | Sort qiling va Binary |
9. Bir nechta element topish
Linear search faqat birinchini topadi. Hammasini:
int find_all(int arr[], int n, int target, int indices[]) {
int count = 0;
for (int i = 0; i < n; i++) {
if (arr[i] == target) {
indices[count++] = i;
}
}
return count;
}10. Element soni
int count_occurrences(int arr[], int n, int target) {
int count = 0;
for (int i = 0; i < n; i++) {
if (arr[i] == target) count++;
}
return count;
}11. Min va Max indexlari
int find_max_index(int arr[], int n) {
int max_idx = 0;
for (int i = 1; i < n; i++) {
if (arr[i] > arr[max_idx]) {
max_idx = i;
}
}
return max_idx;
}12. Big O notation tushunchasi
| Big O | Misol | n=1000 |
|---|---|---|
O(1) | Massiv[i] | 1 |
O(log n) | Binary search | ~10 |
O(n) | Linear search | 1000 |
O(n log n) | Merge sort | ~10,000 |
O(n²) | Bubble sort | 1,000,000 |
O(2ⁿ) | Brute force | astronomik |
Darsdagi topshiriqlar
1 — Linear search
linear.c:
#include <stdio.h>
int linear_search(int arr[], int n, int target) {
for (int i = 0; i < n; i++) {
if (arr[i] == target) return i;
}
return -1;
}
int main(void) {
int arr[] = {12, 45, 7, 23, 89, 34, 56, 11, 78, 90};
int n = 10;
int target;
printf("Topiladigan raqam: ");
scanf("%d", &target);
int result = linear_search(arr, n, target);
if (result != -1) {
printf("Topildi: index %d\n", result);
} else {
printf("Topilmadi\n");
}
return 0;
}2 — Binary search
Dars matnidagi binary search'ni yarating va sinab ko'ring.
Eslatma: massiv sortlangan bo'lsin!
3 — Rekursiv binary
Rekursiv versiyasini yarating va iterativ bilan vaqt taqqoslash (time buyrug'i bilan).
4 — Count occurrences
count.c — element necha marta uchrashini topish.
5 — Find all
find-all.c — barcha indekslarni topish.
int indices[100];
int count = find_all(arr, n, target, indices);
printf("Topildi %d marta:\n", count);
for (int i = 0; i < count; i++) {
printf("Index %d\n", indices[i]);
}6 — Min/Max index
min-max-idx.c — qiymat emas, indexni topish.
7 — Vaqt taqqoslash
speed-test.c:
1 million element massiv yarating (random)
- Linear search vaqti
- Sort qiling
- Binary search vaqti
#include <time.h> va clock() bilan o'lchang.
8 — Range qidiruv
range.c — [a, b] oraliqdagi elementlar:
int count_in_range(int arr[], int n, int a, int b) {
int count = 0;
for (int i = 0; i < n; i++) {
if (arr[i] >= a && arr[i] <= b) count++;
}
return count;
}9 — Element bo'yicha statistika
element-stats.c — Foydalanuvchi raqam bersin:
- Necha marta?
- Birinchi index
- Oxirgi index
- Topilmasa — "topilmadi" deb chiqaring
10 — GitHub
$ mkdir 5-oy-dars-2
$ git add . && git commit -m "feat: dars 2 - search" && git pushLug'at
| Termin | Izoh |
|---|---|
| Linear search | Chiziqli qidiruv |
| Binary search | Yarim-yarimga qidiruv |
| Big O | Algoritm samaradorligi |
| O(n) | Chiziqli — n element = n amal |
| O(log n) | Logarifmik — 1M element = 20 amal |
| O(1) | Doimiy — vaqt o'zgarmaydi |
| Best case | Eng yaxshi holat |
| Worst case | Eng yomon holat |
| Average case | O'rtacha holat |