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.

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}

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.

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}

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

Optimized Search

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

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

Limited Use Cases

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