# Linear and Binary Search, Selection Sort and Bubble Sort

## What is Searching?

- Searching involves finding a specific element in a collection of data.
**Example:**Searching for a name in a phone book to find the corresponding phone number.

## Linear Search

- Linear search is a simple searching algorithm that checks each element in a list or array until the target element is found.
- It begins by checking the first item in the list and then looks at each item to see if it matches the desired value.
- If the element matches the target, the search is successful; otherwise, it continues checking the next element.

**Example :**

```
1int linearSearch(int arr[], int n, int target) {
2
3for (int i = 0; i < n; i++) {
4
5if (arr[i] == target) {
6
7return i; // Element found at index i
8
9}
10
11}
12
13return -1; // Element not found
14
15}
```

**Another Example :**

```
1int main() {
2
3int array[] = {10, 20, 30, 40, 50};
4
5int size = sizeof(array) / sizeof(array[0]);
6
7int target = 30;
8
9int result = linearSearch(array, size, target);
10
11if (result != -1) {
12
13printf("Element found at index %d\n", result);
14
15} else {
16
17printf("Element not found\n");
18
19}
20
21return 0;
22
23}
```

## Advantages of Linear Search

**Simplicity:**Linear search is straightforward to implement, making it suitable for beginners and simple applications.**Flexibility:**It can be applied to both sorted and unsorted lists or arrays, offering versatility in various scenarios.**Easy to Understand:**The logic behind linear search is easy to understand and conceptualize, making it accessible for programmers.

### Disadvantages

**Inefficiency with Large Data Sets:**In large lists or arrays, linear search becomes inefficient as it needs to check every element sequentially.**Performance Degradation:**As the size of the list increases, the time complexity of linear search grows linearly, leading to slower search times.**High Time Complexity:**The worst-case time complexity of linear search is O(n),- where 'n' is the number of elements in the list, indicating slower performance for larger datasets.

## Binary Search

- Binary search is a more efficient searching algorithm applicable to sorted arrays or lists.
- It keeps dividing the search range into halves until it finds the desired item.
- It requires the array or list to be sorted beforehand.

**Example :**

```
1int binarySearch(int arr[], int left, int right, int target) {
2
3while (left <= right) {
4
5int mid = left + (right - left) / 2;
6
7if (arr[mid] == target) {
8
9return mid; // Element found at index mid
10
11}
12
13if (arr[mid] < target) {
14
15left = mid + 1;
16
17} else {
18
19right = mid - 1;
20
21}
22
23}
24
25return -1; // Element not found
26
27}
```

**Example 2:**

```
1int main() {
2
3int array[] = {10, 20, 30, 40, 50};
4
5int size = sizeof(array) / sizeof(array[0]);
6
7int target = 30;
8
9int result = binarySearch(array, 0, size - 1, target);
10
11if (result != -1) {
12
13printf("Element found at index %d\n", result);
14
15} else {
16
17printf("Element not found\n");
18
19}
20
21return 0;
22
23}
```

## Advantages of Binary Search

### Efficient for Large Lists

- Binary search is highly efficient for large lists because it reduces the search space by half in each iteration.
- This logarithmic time complexity (O(log n)) makes it suitable for handling vast amounts of data.

### Fast Searching

Due to its logarithmic time complexity, binary search performs significantly faster than linear search, especially as the size of the list increases.

### Optimized Search

It is ideal for sorted lists or arrays, where it optimally locates the target element by repeatedly dividing the search interval.

## Disadvantages of Binary Search

### Requires Sorted Data

- One major limitation of binary search is that it requires the list to be sorted beforehand.
- Sorting the data can be time-consuming and may require additional processing steps.

### Complex Implementation

- Compared to linear search, binary search is more complex to implement due to
- its divide-and-conquer approach and the need for handling indices and midpoints.

### Limited Applicability

- Binary search is suitable only for sorted lists or arrays.
- If the data is unsorted or frequently changing, binary search may not be the best choice.

### Selection Sort

- Selection Sort is an easy to use sorting technique that involves choosing the smallest or largest item from the unsorted part of the list.
- part of the list and swapping it with the element at the beginning of the unsorted part.

### Advantages of Selection Sort

**Simple Implementation:**Selection Sort is easy to understand and implement, making it a good choice for basic sorting tasks.**Space Efficiency:**Selection Sort requires minimal additional memory space,- as it performs in-place sorting by swapping elements within the array.
**Stability:**Selection Sort is a stable sorting algorithm, meaning it preserves the relative order of equal elements in the sorted array.

### Disadvantages of Selection Sort

#### Inefficiency for Large Lists

Selection Sort has a

**time complexity of O(n^2)**, making it inefficient for large lists or arrays as the number of comparisons and swaps increases significantly.#### Lack of Adaptiveness

- Unlike some other sorting algorithms, Selection Sort does not adapt its
- approach based on the initial state of the list, leading to similar comparisons and swaps even for partially sorted arrays.

#### Not Suitable for Linked Lists

While Selection Sort is suitable for arrays, it is not efficient for sorting linked lists due to its swapping mechanism.

#### Limited Use Cases

Selection Sort is typically used for educational purposes or when simplicity is prioritized over performance in small-scale applications.

```
1#include <stdio.h>
2
3void selectionSort(int arr[], int n) {
4 int i, j, minIndex, temp;
5 for (i = 0; i < n - 1; i++) {
6 minIndex = i;
7 for (j = i + 1; j < n; j++) {
8 if (arr[j] < arr[minIndex]) {
9 minIndex = j;
10 }
11 }
12 if (minIndex != i) {
13 temp = arr[i];
14 arr[i] = arr[minIndex];
15 arr[minIndex] = temp;
16 }
17 }
18}
19
20int main() {
21 int arr[] = {64, 25, 12, 22, 11};
22 int n = sizeof(arr) / sizeof(arr[0]);
23 selectionSort(arr, n);
24 printf("Sorted array: ");
25 for (int i = 0; i < n; i++) {
26 printf("%d ", arr[i]);
27 }
28 printf("\n");
29 return 0;
30}
31
```

## Conclusion

We have covered the basics of Searching and Sorting: Linear and Binary Search, Selection Sort, Bubble Sort, Insertion Sort, Merge Sort, Comparison of Searching and Sorting Algorithms.