# Exploring Array Searching in C++ | Data Structure and Algorithm

## **Introduction**

Array searching is a fundamental operation in computer science and is used to find the presence of an element within a collection of data. Two common methods for array searching are **linear search** and **binary search.**

## **Linear Search**

Linear search is a simple search algorithm that checks every element in a collection until a match is found. It starts from the beginning of the array and iterates through each element until the desired element is found or the end of the array is reached.

**Pseudocode:**

```cpp
function linearSearch(array, target):
    for each element in array:
        if element equals target:
            return index of element
    return -1  // element not found
```

**Time Complexity:**

* Best Case: O(1) - when the target element is found at the beginning
    
* Worst Case: O(n) - when the target element is at the end or not present
    
* Average Case: O(n)
    

**Space Complexity:** O(1) - constant space is used

## **Binary Search**

Binary search is an efficient algorithm for finding a target element in a sorted collection. It works by repeatedly dividing the search range in half.

**Pseudocode:**

```cpp
function binarySearch(array, target):
    left = 0
    right = length of array - 1
    while left <= right:
        mid = (left + right) / 2
        if array[mid] equals target:
            return mid  // target found
        else if array[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1  // target not found
```

**Time Complexity:**

* Best Case: O(1) - when the target element is found at the middle
    
* Worst Case: O(log n) - when the array is large
    
* Average Case: O(log n)
    

**Space Complexity:** O(1) - constant space is used

## **C++ Implementation**

Here's a simple C++ program showcasing both linear and binary search:

```cpp
#include <iostream>

using namespace std;

// Linear search without using STL
int linearSearch(const int array[], int size, int target) {
    for (int i = 0; i < size; ++i) {
        if (array[i] == target) {
            return i;
        }
    }
    return -1;
}

// Binary search without using STL
int binarySearch(const int array[], int size, int target) {
    int left = 0;
    int right = size - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (array[mid] == target) {
            return mid;
        } else if (array[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return -1;
}

int main() {
    int sortedArray[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    int size = sizeof(sortedArray) / sizeof(sortedArray[0]);
    int target = 7;

    // Linear Search
    int linearResult = linearSearch(sortedArray, size, target);
    cout << "Linear Search Result: " << linearResult << endl;

    // Binary Search
    int binaryResult = binarySearch(sortedArray, size, target);
    cout << "Binary Search Result: " << binaryResult << endl;

    return 0;
}
```

In this program, we define functions for both linear and binary search and demonstrate their usage with a sorted array.