by Jasleen Chhabra | Updated on 24 August 2024

Searching is one of the most fundamental operations performed on arrays. It involves locating the position of a specific element within the array. Understanding and efficiently implementing search operations is crucial for many programming tasks. This guide will explore different searching techniques, their applications, and provide practical examples.

Importance of Searching

Searching is essential for:

• Locating specific data within a large dataset.
• Performing operations like insertions, deletions, and updates based on the position of elements.
• Enhancing the efficiency of data retrieval in various applications.

Types of Searching Techniques

1. Linear Search: A simple search method that checks each element of the array sequentially until the desired element is found or the end of the array is reached.
2. Binary Search: An efficient search method that works on sorted arrays. It repeatedly divides the search interval in half and compares the target value with the middle element.

---

Linear Search

Linear search is straightforward and works on both sorted and unsorted arrays. It is easy to implement but can be inefficient for large datasets.

Algorithm for Linear Search

1. Start: Initialize the process.
2. Iterate: Traverse the array from the first element to the last.
3. Compare: Check if the current element matches the target value.
4. Return: If a match is found, return the index of the element. If no match is found, return -1.
5. End: Terminate the process.

Example of Linear Search in C++

#include <iostream>
using namespace std;

int linearSearch(int arr[], int n, int x) {
    // Step 1: Start
    // Step 2: Iterate
    for (int i = 0; i < n; i++) {
        // Step 3: Compare
        if (arr[i] == x) {
            // Step 4: Return
            return i;
        }
    }
    // Step 4: Return
    return -1;
    // Step 5: End
}

int main() {
    int arr[] = {10, 20, 30, 40, 50};
    int n = sizeof(arr) / sizeof(arr[0]);
    int x = 30;  // Element to search for

    int result = linearSearch(arr, n, x);

    if (result != -1) {
        cout << "Element found at index " << result << endl;
    } else {
        cout << "Element not found in the array" << endl;
    }

    return 0;
}
 

---

Binary Search

Binary search is efficient but requires the array to be sorted. It repeatedly divides the search interval in half and compares the target value with the middle element.

Algorithm for Binary Search

1. Start: Initialize the process.
2. Sort: Ensure the array is sorted.
3. Divide: Set the low and high indices.
4. Compare:
   • Calculate the middle index.
   • If the middle element matches the target, return the index.
   • If the target is less than the middle element, search the left subarray.
   • If the target is greater than the middle element, search the right subarray.
5. Repeat: Continue the process until the element is found or the subarray size becomes zero.
6. End: Terminate the process.

Example of Binary Search in C++

#include <iostream>
using namespace std;

int binarySearch(int arr[], int low, int high, int x) {
    while (low <= high) {
        // Step 3: Divide
        int mid = low + (high - low) / 2;

        // Step 4: Compare
        if (arr[mid] == x) {
            // If the element is present at the middle
            return mid;
        }
        if (arr[mid] < x) {
            // If the element is present in the right subarray
            low = mid + 1;
        } else {
            // If the element is present in the left subarray
            high = mid - 1;
        }
    }

    // Element is not present in the array
    return -1;
}

int main() {
    int arr[] = {10, 20, 30, 40, 50};
    int n = sizeof(arr) / sizeof(arr[0]);
    int x = 30;  // Element to search for

    int result = binarySearch(arr, 0, n - 1, x);

    if (result != -1) {
        cout << "Element found at index " << result << endl;
    } else {
        cout << "Element not found in the array" << endl;
    }

    return 0;
}
 

Choosing the Right Search Technique

• Linear Search: Suitable for small or unsorted arrays. Easy to implement but can be inefficient for large datasets.
• Binary Search: Ideal for large, sorted arrays. More efficient but requires the array to be sorted beforehand.

Conclusion

Searching in arrays is a fundamental operation in programming. Understanding and implementing efficient search techniques, like linear and binary search, can significantly improve the performance of your applications. This guide provides a comprehensive overview of these techniques, from basic concepts to practical implementation, ensuring you have the knowledge to handle array searching effectively.

---

---