**Searching algorithms are implemented to search for elements and retrieve their values from any data structure. Based on the search operation, searching algorithms can be classified into two categories:**

**Sequential Search Algorithm:**In a sequential search algorithm, each element of the list is traversed and checked. For example, Linear Search.**Interval Search Algorithm:**In an interval search algorithm, search is performed on a sorted data structure. These algorithms are much more efficient as they divide the search space in half subsequently. For example, Binary search.

A sorting algorithm can be judged based on the following criteria:

- Completeness
- Optimality
- Search Complexity
- Time Complexity

**Table of Contents**

### Linear Search

**Linear search is a simple searching algorithm wherein each data element in a list is traversed and checked. If the element to be searched is found, we return its value. Otherwise, an error message is displayed. Linear search is a type of sequential search.**

#### Implementation of Linear Search

The linear search algorithm is based on the following steps:

- We iterate over the given list and compare each value with the value to be searched.
- If a match is found, we return the index position of that element in the list.
- Otherwise, we return -1 to indicate that the element does not exist in the given list.

```
#Function to implement Linear Search
def linearSearch(tempList, value):
for i in range(len(tempList)):
if tempList[i] == value:
return i
return -1
print(linearSearch([20,40,30,50,90], 50))
#Output
3
```

#### Time and Space Complexity

The time complexity for the linear search algorithm is **O(N)** as we iterate over the entire list to search for the given element. The space complexity is **O(1)** as no additional memory is required.

### Binary Search

**Binary search is a searching algorithm wherein elements are searched from a sorted list or array. Binary search is an interval search algorithm. **In the implementation of the algorithm, the list is broken down into halves based on the values of the elements. Then, the same process is repeated on the sub-lists and searched further till the required element is found.

#### Implementation of Binary Search

- We are given a list of sorted elements and let the element to be searched be
`value`

.

- Set two pointers
`start`

and`end`

at the lowest and the highest positions respectively.

- Find the middle value of the list((start+end)/2).

- If
`value`

is greater than`middle`

set the pointers to the right of middle, creating a new sub-list. Otherwise, move to the left and create the new seub-list.

- Keep comparing the middle value to the value to be searched until the given element is found.

```
#Function to implement Binary Search
import math
def binarySearch(tempList, value):
start = 0
end = len(tempList)-1
middle = math.floor((start+end)/2)
while not(tempList[middle]==value) and start<=end:
if value < tempList[middle]:
end = middle - 1
else:
start = middle + 1
middle = math.floor((start+end)/2)
# print(start, middle, end)
if tempList[middle] == value:
return middle
else:
return -1
searchList = [8, 9, 12, 15, 17, 19, 20, 21, 28]
print(binarySearch(searchList, 15))
#Output
3
```

#### Time and Space Complexity

The time complexity for binary search is **O(logN)** because the list is continuously divided into halves and elements of the sub-lists are searched further. The space complexity is **O(1)** as no additional memory is required.