Searching an Element in an Array in C++

 

In C++, you can search for an element in an array using various methods. One of the most basic approaches is using a linear search, where you traverse the array from the start to the end and check if the element matches.

---

1️⃣ Linear Search in C++

Steps for Linear Search:

1. Traverse through the array from the first to the last element.
2. For each element, check if it matches the target element.
3. If a match is found, return the index of the element.
4. If the loop ends and no match is found, return a value indicating the element is not in the array (e.g., -1).

Example: Linear Search Implementation

#include <iostream>
using namespace std;

int linearSearch(int arr[], int size, int target) {
    // Traverse the array
    for (int i = 0; i < size; i++) {
        if (arr[i] == target) {
            return i;  // Element found, return its index
        }
    }
    return -1;  // Element not found, return -1
}

int main() {
    int arr[] = {10, 20, 30, 40, 50};
    int size = sizeof(arr) / sizeof(arr[0]);  // Calculate the number of elements
    int target;

    // Input target element to search
    cout << "Enter the element to search: ";
    cin >> target;

    int result = linearSearch(arr, size, target);

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

    return 0;
}

Explanation:

1. The linearSearch function takes the array arr[], its size, and the target element to search for.
2. It loops through each element of the array. If the target is found, it returns the index.
3. If the target is not found after checking all elements, it returns -1.

Output (Example when target = 30):

Enter the element to search: 30
Element 30 found at index 2

Output (Example when target = 60):

Enter the element to search: 60
Element 60 not found in the array.

---

2️⃣ Binary Search in C++

If the array is sorted, you can use a more efficient algorithm called Binary Search. Binary search works by repeatedly dividing the search interval in half. If the value of the search key is less than the item in the middle of the interval, the interval is narrowed to the lower half. Otherwise, it narrows the interval to the upper half.

Steps for Binary Search:

1. Sort the array (if it's not already sorted).
2. Set the initial search range as the entire array.
3. Compare the target element with the middle element of the array.
4. If they are equal, return the middle index.
5. If the target is smaller, search the left half.
6. If the target is larger, search the right half.
7. Repeat until the target is found or the search range is empty.

Example: Binary Search Implementation

#include <iostream>
#include <algorithm>  // For sorting
using namespace std;

int binarySearch(int arr[], int size, int target) {
    int low = 0, high = size - 1;

    while (low <= high) {
        int mid = low + (high - low) / 2;

        // Check if the target is present at mid
        if (arr[mid] == target) {
            return mid;  // Element found at mid
        }

        // If target is smaller, ignore the right half
        if (arr[mid] > target) {
            high = mid - 1;
        }
        // If target is larger, ignore the left half
        else {
            low = mid + 1;
        }
    }
    return -1;  // Element not found
}

int main() {
    int arr[] = {10, 20, 30, 40, 50};
    int size = sizeof(arr) / sizeof(arr[0]);  // Calculate the number of elements
    int target;

    // Sort the array (if not sorted already)
    sort(arr, arr + size);

    // Input target element to search
    cout << "Enter the element to search: ";
    cin >> target;

    int result = binarySearch(arr, size, target);

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

    return 0;
}

Explanation:

1. The binarySearch function performs the search by dividing the array and checking the middle element.
2. The array is sorted using sort() from <algorithm> to ensure binary search works.
3. The target element is compared with the middle value, and the search interval is adjusted accordingly.

Output (Example when target = 30):

Enter the element to search: 30
Element 30 found at index 2

Output (Example when target = 60):

Enter the element to search: 60
Element 60 not found in the array.

---

3️⃣ Key Points to Remember:

• Linear Search is simple but has a time complexity of O(n), meaning it may take longer for larger arrays.
• Binary Search is efficient with a time complexity of O(log n), but it requires the array to be sorted.
• For unsorted arrays, linear search is the preferred method.
• Binary Search can be faster for larger arrays that are already sorted.

Would you like to explore more advanced search techniques or sorting algorithms in C++?