Linear Search

Chiziqli qidiruv (Linear Search) — bu eng sodda ketma-ket qidiruv algoritmi bo'lib, u ro'yxatning bir boshidan boshlab toki qidirilayotgan element topilguniga qadar yoki ro'yxat tugaguniga qadar har bir elementni birma-bir tekshirib chiqadi.

U elementlar oldindan saralangan bo'lishini talab qilmaydi.

Chiziqli qidiruv qanday ishlaydi?

Faraz qilaylik, quyidagi massivdan k = 1 elementini qidirmoqchimiz:

Qidiruv o'tkaziladigan massiv (Array to be searched for)

1. Massivning birinchi elementidan boshlab, k qiymatini har bir x elementi bilan taqqoslaymiz:

Har bir element bilan ketma-ket taqqoslash

2. Agar x == k bo'lsa, ushbu element joylashgan indeksni qaytaramiz:

Qidirilgan element topildi (indeksi: 5)

3. Agar massivning oxirigacha borib ham element topilmasa, -1 (topilmadi) qiymati qaytariladi.

Chiziqli qidiruv algoritmi

LinearSearch(array, key)
  for each item in array
    if item == key
      return its index
  return -1

Dasturiy namunalar

// Go tilida Linear Search algoritmi
package main

import "fmt"

func linearSearch(arr []int, key int) int {
	for i, val := range arr {
		if val == key {
			return i // Element topilgan indeks
		}
	}
	return -1 // Topilmadi
}

func main() {
	arr := []int{2, 4, 0, 1, 9}
	x := 1

	result := linearSearch(arr, x)

	if result == -1 {
		fmt.Println("Element massivda mavjud emas")
	} else {
		fmt.Printf("Element %d-indeksda topildi\n", result)
	}
}

Chiziqli qidiruvning murakkabligi

Vaqt murakkabligi

• Eng yaxshi holat (Best Case Complexity): O(1) — agar qidirilayotgan element massivning eng birinchi pozitsiyasida turgan bo'lsa.
• Eng yomon holat (Worst Case Complexity): O(n) — agar element massivning eng oxirida bo'lsa yoki umuman mavjud bo'lmasa (barcha n ta element tekshiriladi).
• O'rtacha holat (Average Case Complexity): O(n).

Xotira murakkabligi

• Xotira murakkabligi O(1) ga teng (qo'shimcha xotira talab qilinmaydi).

Chiziqli qidiruvning qo'llanilishi

• Saralanmagan yoki kichik hajmdagi ro'yxatlarda element izlashda.
• Yagona marta qidiruv o'tkazilganda (massivni oldindan saralashga vaqt sarflamaslik uchun).