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

## Data Structure Algorithm

## Table of contents

**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:**

```
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:**

```
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:

```
#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.