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 5

5. 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 5

7. 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 push

Lug'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

Keyingi dars

3-dars: Bubble Sort →