Linear Search क्या है

Linear search एक line में एक friend ढूंढने जैसा है हर face को एक-एक करके front से check करके जब तक आप उन्हें न ढूंढ लें।

In this page:

What is Linear Search
How It Works
Best and Worst Case
Complexity
When to Use

Syntax

markup

for i in range(len(arr)):
    if arr[i] == target:
        return i
return -1

What is Linear Search

Linear search किसी collection के हर element को एक समय में एक जांचता है, पहले से आखिरी तक, जब तक यह target value न ढूंढे या इसके बिना ढूंढे आखिर तक न पहुंच जाए। यह सबसे straightforward search strategy है और काम करता है चाहे data sorted हो या नहीं।

उदाहरण: What is Linear Search

#include <iostream>
using namespace std;
int main() {
	int arr[] = {8, 3, 5, 1, 9};
	int target = 5;
	for (int i = 0; i < 5; i++) {
		if (arr[i] == target) { cout << "Found at index " << i; break; }
	}
	return 0;
}

public class Main {
	public static void main(String[] args) {
		int[] arr = {8, 3, 5, 1, 9};
		int target = 5;
		for (int i = 0; i < arr.length; i++) {
			if (arr[i] == target) { System.out.println("Found at index " + i); break; }
		}
	}
}

arr = [8, 3, 5, 1, 9]
target = 5
for i, x in enumerate(arr):
    if x == target:
        print("Found at index", i)
        break

#include <stdio.h>
int main() {
	int arr[] = {8, 3, 5, 1, 9};
	int target = 5;
	for (int i = 0; i < 5; i++) {
		if (arr[i] == target) { printf("Found at index %d", i); break; }
	}
	return 0;
}

How It Works

Algorithm target को current element से compare करता है; अगर वे match करें, search रुक जाता है और वह position return करता है, और अगर नहीं, यह अगले element पर move करता है और comparison दोहराता है जब तक एक match न मिले या collection खत्म न हो जाए।

उदाहरण: How It Works

#include <iostream>
using namespace std;
int main() {
	int arr[] = {8, 3, 5, 1, 9};
	int target = 1;
	for (int i = 0; i < 5; i++) {
		cout << "Checking index " << i << ": " << arr[i] << endl;
		if (arr[i] == target) { cout << "Match found"; break; }
	}
	return 0;
}

public class Main {
	public static void main(String[] args) {
		int[] arr = {8, 3, 5, 1, 9};
		int target = 1;
		for (int i = 0; i < arr.length; i++) {
			System.out.println("Checking index " + i + ": " + arr[i]);
			if (arr[i] == target) { System.out.println("Match found"); break; }
		}
	}
}

arr = [8, 3, 5, 1, 9]
target = 1
for i, x in enumerate(arr):
    print("Checking index", i, ":", x)
    if x == target:
        print("Match found")
        break

#include <stdio.h>
int main() {
	int arr[] = {8, 3, 5, 1, 9};
	int target = 1;
	for (int i = 0; i < 5; i++) {
		printf("Checking index %d: %d\n", i, arr[i]);
		if (arr[i] == target) { printf("Match found"); break; }
	}
	return 0;
}

Best and Worst Case

Best case में target बिल्कुल पहला जांचा गया element है, सिर्फ एक comparison चाहिए। Worst case में target आखिरी element है (या बिल्कुल मौजूद नहीं), खत्म करने से पहले हर single element जांचना चाहिए।

उदाहरण: Best and Worst Case

#include <iostream>
using namespace std;
int main() {
	int arr[] = {8, 3, 5, 1, 9};
	cout << "Best case: target=8 found in 1 comparison. Worst case: target=9 found in 5 comparisons";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("Best case: target=8 found in 1 comparison. Worst case: target=9 found in 5 comparisons");
	}
}

print("Best case: target=8 found in 1 comparison. Worst case: target=9 found in 5 comparisons")

#include <stdio.h>
int main() {
	printf("Best case: target=8 found in 1 comparison. Worst case: target=9 found in 5 comparisons");
	return 0;
}

Complexity

Linear search worst case में O(n) time लेता है क्योंकि इसे हर element examine करना पड़ सकता है, और O(1) extra space क्योंकि इसे सिर्फ current position track करनी है — कोई additional data structures की ज़रूरत नहीं।

उदाहरण: Complexity

#include <iostream>
using namespace std;
int main() {
	cout << "Linear search: O(n) worst-case time, O(1) extra space";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("Linear search: O(n) worst-case time, O(1) extra space");
	}
}

print("Linear search: O(n) worst-case time, O(1) extra space")

#include <stdio.h>
int main() {
	printf("Linear search: O(n) worst-case time, O(1) extra space");
	return 0;
}

When to Use

चूंकि यह ordering के बारे में कोई assumptions नहीं बनाता, linear search unsorted data या पहले sort करने की परेशानी के लायक बहुत छोटे data के लिए सही choice है; एक बार data sorted हो जाए, binary search जैसे faster options setup cost के लायक हो जाते हैं।

उदाहरण: When to Use

#include <iostream>
using namespace std;
int main() {
	cout << "Best for unsorted data or collections too small to justify sorting first";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("Best for unsorted data or collections too small to justify sorting first");
	}
}

print("Best for unsorted data or collections too small to justify sorting first")

#include <stdio.h>
int main() {
	printf("Best for unsorted data or collections too small to justify sorting first");
	return 0;
}

Chapter Quiz — Complete all 5 topics to unlock

0/5 topics done

Complete these topics first:

← Previous Lesson Sorting Comparison Next Lesson → Binary Search