Linear Search

 

What is Searching?

Searching is the process of finding a particular item (called key) from a collection of items (like an array, list, or database).

• If the item is found, we usually return its position (index).

• If the item is not found, we indicate that the search was unsuccessful.

Searching is very important in real-world applications like:

• Finding a name in a contact list 📞

• Searching a product on an online store 🛒

• Looking up a word in a dictionary 📖

---

🌟 What are Search Algorithms?

Search Algorithms are special methods or procedures to locate the target value within a dataset.

Common search algorithms include:

• Linear Search

• Binary Search

• Hashing-based Search

• Search Trees (like Binary Search Trees)

---

🌟 Linear Search (Detailed Explanation)

Linear Search is the simplest search algorithm.

It checks each element of the list one by one until:

• It finds the target (success) ✅

• Or reaches the end without finding it (failure) ❌

---

📋 Linear Search Algorithm

1. Start from the first element of the array.

2. Compare the target value with the current element.

3. If they are equal, return the index (element found).

4. If not, move to the next element.

5. Repeat steps 2–4 until:

   • The element is found, or

   • The entire array is traversed.

6. If not found after the whole array, report that the element does not exist.

---

📈 Time Complexity

Case	Complexity
Best Case (first element)	O(1)
Worst Case (last element or not present)	O(n)
Average Case	O(n)

n = number of elements.

---

✏️ Simple Example

Suppose we have the array:

[10, 25, 30, 45, 50]

and we want to find 30.

• Compare 10 → no

• Compare 25 → no

• Compare 30 → yes! (found at index 2)

C Program- Linear Search

#include <stdio.h>

int linearSearch(int arr[], int n, int key) {

    for (int i = 0; i < n; i++) {

        if (arr[i] == key)

            return i; // Key found at index i

    }

    return -1; // Key not found

}

int main() {

    int arr[100], n, key, result;

    printf("Enter number of elements: ");

    scanf("%d", &n);

    printf("Enter elements:\n");

    for (int i = 0; i < n; i++)

        scanf("%d", &arr[i]);

    printf("Enter the key to search: ");

    scanf("%d", &key);

    result = linearSearch(arr, n, key);

    if (result == -1)

        printf("Key not found.\n");

    else

        printf("Key found at index %d.\n", result);

    return 0;

}

Output

Enter number of elements: 5

Enter elements:

6 7 8 9 2

Enter the key to search: 8

Key found at index 2

Enter number of elements: 5

Enter elements:

5 4 2 7 8

Enter the key to search: 9

Key not found.