## Introduction

Hello Ninja, I hope you are doing great. Do you know about Searching and Sorting? If not, don't worry. We are here to enrich your knowledge and clear all your doubts.

This article will discuss searching and sorting, along with their different algorithms. We will also analyze the time and space complexity of the algorithms. This article will show the significant difference between Searching and Sorting on specific parameters.

## Searching

Searching is finding a particular item in a given list of items. It decides whether an element we are searching for is present or not. A search algorithm is an algorithm that accepts an argument "x"’ and tries to find an item in a given list whose value is equal to "x."

Searching for an element in a list can be done using Sequential search and Interval search.

The image above shows searching for an element in a sorted array using binary search.

### Code

```
#include <bits/stdc++.h>
using namespace std;
int Binary_Search(vector <int> &my_List, int element) {
int start = 0, end = my_List.size() - 1, index = -1;
while(start <= end) {
// find a mid
int mid = (start + end) / 2;
// check if our element is less than or equal to the element present at the mid index
if(my_List[mid] >= element) {
// now element present at mid can be our potential answer
index = mid;
// reduce the range because our element can't be at any index > mid
end = mid - 1;
}
else {
// reduce the range because our element can't be at any index < mid
start = mid + 1;
}
}
if(index != -1) {
if(my_List[index] != element) index = -1;
}
return index;
}
int main() {
vector <int> my_List = {1, 4, 15, 18, 22, 25};
int element = 18;
// search '18' in a given list and print its index
cout << Binary_Search(my_List, element);
return 0;
}
```

### Output:

`3`

The code above uses a __binary search algorithm__ to search a given element from the list.

### Sequential Search

It is also known as Linear Search. It starts at the beginning of the list and compares every value on the list with the target value. If the target value matches the value in a list, then it returns the index of that element; otherwise, it returns -1.

#### Time Complexity

In the worst case (when the element we are searching for is present at the end of the list) we have to traverse the whole array. So, its Worst case time complexity will be O(n).

In the Best case, the element will be present at the beginning of the list. So we don’t need to traverse the array. Hence its Best case time complexity will be O(1).

#### Space Complexity

We don’t need any auxiliary space for this technique. So its space complexity will be O(1);

### Interval Search

In this algorithm we only check certain parts of the dataset. Binary search is an example of an interval search algorithm. Binary Search works on sorted lists i.e., the list must be in increasing or decreasing order. It is based on a divide and conquer algorithm in which we compare our target value with the middle element of the list and based on that we reduce our search space by half. We continue this until we find our target element or our search space reduces to 1.

#### Time Complexity

The Worst case occurs when the algorithm keeps searching for the target until our search space reduces to 1. Since the number of comparisons are logn. So its Worst case time complexity will be O(logn).

The Best case occurs when the target is present in the middle. So only one comparison will be needed. Hence, its Best case time complexity will be O(1).

#### Space Complexity

We don’t need any auxiliary space for this technique. So its space complexity will be O(1);

Also Read - __Selection Sort in C__