Searching

Linear Search

• In this technique key element is compared with each element of the array.

Basic procedure ↓

                
for(i = 0; i < length; i++)
{
    if(key == A[i])
        return i;
}
return -1;
                
            

Time complexity of Linear Search

• The linear search loop will run minimum for 1 time (when the key element if the first element of the array).
  • Best case time - O(1)
• And maximum for 'n' time (when the key element is not present).
  • Worst case time - O(n)
• Average = (1 + 2 + 3 + ... + n)/n = ((n(n + 1))/2)/n = (n + 1 ) / 2 - degree 1 polynomial
  • Average case time - O(n)

                   
#include <stdio.h>
int linearSearch(int arr[], int key)
{
    int i;
    int size = 10;
    for (i = 0; i < size; i++)
    {
        if (key == arr[i])
            return i;
    }
    return -1;
}
int main()
{
    int arr[10] = {3, 2, 4, 5, 6, 7, 8, 9, 11, 23};
    printf("The element is present at index %d", linearSearch(arr, 6));
    return 0;
}
                   
               

Binary Search

• For performing binary search the pre-requisite is that the list of element must be sorted.
• It is known as binary search because it splits the array into two until the middle element in not equal to the key element.
• The time complexity of binary search is O(log n), where "n" is the number of elements in the sorted array.
• Binary search operates by repeatedly dividing the search space in half, discarding one half each time based on a comparison with the target element. This logarithmic behavior arises from the fact that with each iteration, the search space is effectively halved. As a result, binary search can quickly narrow down the search to the desired element or determine its absence in logarithmic time.

                
Algorithm BinSearch(l, h, key)
{
    while(l <= h)
    {
        mid = (l + h) / 2;
        if(key == A[mid])
            return mid;
        else if(key < A[mid])
            h = mid - 1;
        else 
            l = mid + 1;
    }
    return -1;
}
                
            

Code ↓

                   
#include <stdio.h>
#define MAX 10
int arr[MAX] = {12, 24, 25, 36, 45, 46, 47, 48, 59, 63};
int BinarySearch(int key)
{
    int l, mid, h;
    l = 0;
    h = MAX - 1;
    while (l <= h)
    {
        mid = (l + h) / 2;
        if (key == arr[mid])
            return mid;
        else if (key < arr[mid])
            h = mid - 1;
        else
            l = mid + 1;
    }
    return -1;
}
int main()
{
    printf("Value is present at index %d\n", BinarySearch(36));
    return 0;
}