Introduction to Searching Algorithms

What if you have to write a program to search a given number in an array? How will you do it?
Well, to search an element in a given array, there are two popular algorithms available:
  1. Linear Search
  2. Binary Search

Linear Search

Linear search is a very basic and simple search algorithm. In Linear search, we search an element or value in a given array by traversing the array from the starting, till the desired element or value is found.
It compares the element to be searched with all the elements present in the array and when the element is matched successfully, it returns the index of the element in the array, else it return -1.
Linear Search is applied on unsorted or unordered lists, when there are fewer elements in a list.

Features of Linear Search Algorithm

  1. It is used for unsorted and unordered small list of elements.
  2. It has a time complexity of O(n), which means the time is linearly dependent on the number of elements, which is not bad, but not that good too.
  3. It has a very simple implementation.

Implementing Linear Search

Linear search is a very basic and simple search algorithm. In Linear search, we search an element or value in a given array by traversing the array from the starting, till the desired element or value is found.
The time complexity of Linear search algorithm is O(n), we will analyse the same and see why it is O(n) after implementing it.
Following are the steps of implementation that we will be following:
  1. Traverse the array using a for loop.
  2. In every iteration, compare the target value with the current value of the array.
    • If the values match, return the current index of the array.
    • If the values do not match, move on to the next array element.
  3. If no match is found, return -1.
To search the number 5 in the array given below, linear search will go step by step in a sequential order starting from the first element in the given array.
{ 8 2 6 3 5 }


/* 
    below we have implemented a simple function 
    for linear search in C
    
    - values[] => array with all the values
    - target => value to be found
    - n => total number of elements in the array
*/
int linearSearch(int values[], int target, int n)
{
    for(int i = 0; i < n; i++)
    {
        if (values[i] == target) 
        {       
            return i; 
        }
    }
    return -1;
}

Some Examples with Inputs

OUTPUT:
Input: values[] = {5, 34, 65, 12, 77, 35}
target = 77
Output: 4
Input: values[] = {101, 392, 1, 54, 32, 22, 90, 93}
target = 200
Output: -1 (not found)

Binary Search

Binary Search is used with sorted array or list. In binary search, we follow the following steps:
  1. We start by comparing the element to be searched with the element in the middle of the list/array.
  2. If we get a match, we return the index of the middle element.
  3. If we do not get a match, we check whether the element to be searched is less or greater than in value than the middle element.
  4. If the element/number to be searched is greater in value than the middle number, then we pick the elements on the right side of the middle element(as the list/array is sorted, hence on the right, we will have all the numbers greater than the middle number), and start again from the step 1.
  5. If the element/number to be searched is lesser in value than the middle number, then we pick the elements on the left side of the middle element, and start again from the step 1.
Binary Search is useful when there are large number of elements in an array and they are sorted.
So a necessary condition for Binary search to work is that the list/array should be sorted.

Features of Binary Search

  1. It is great to search through large sorted arrays.
  2. It has a time complexity of O(log n) which is a very good time complexity.
  3. It has a simple implementation.

Implementing Binary Search Algorithm

Binary Search is applied on the sorted array or list of large size. It's time complexity of O(log n) makes it very fast as compared to other sorting algorithms. The only limitation is that the array or list of elements must be sorted for the binary search algorithm to work on it.

Following are the steps of implementation that we will be following:
  1. Start with the middle element:
    • If the target value is equal to the middle element of the array, then return the index of the middle element.
    • If not, then compare the middle element with the target value,
      • If the target value is greater than the number in the middle index, then pick the elements to the right of the middle index, and start with Step 1.
      • If the target value is less than the number in the middle index, then pick the elements to the left of the middle index, and start with Step 1.
  2. When a match is found, return the index of the element matched.
  3. If no match is found, then return -1
/*
    function for carrying out binary search on given array
    - values[] => given sorted array
    - len => length of the array
    - target => value to be searched
*/
int binarySearch(int values[], int len, int target)
{
    int max = (len - 1);
    int min = 0;
    
    int guess;  // this will hold the index of middle elements
    int step = 0;  // to find out in how many steps we completed the search
    
    while(max >= min)
    {
        guess = (max + min) / 2;
        // we made the first guess, incrementing step by 1
        step++;
        
        if(values[guess] ==  target)
        {
            printf("Number of steps required for search: %d \n", step);
            return guess;
        }
        else if(values[guess] >  target) 
        {
            // target would be in the left half
            max = (guess - 1);
        }
        else
        {
            // target would be in the right half
            min = (guess + 1);
        }
    }
 
    // We reach here when element is not 
    // present in array
    return -1;
}
 
int main(void)
{
    int values[] = {13, 21, 54, 81, 90};
    int n = sizeof(values) / sizeof(values[0]);
    int target = 81;
    int result = binarySearch(values, n, target);
    if(result == -1)
    {  
        printf("Element is not present in the given array.");
    }
    else
    {
        printf("Element is present at index: %d", result);
    }
    return 0;
}

Now let's try to understand, why is the time complexity of binary search O(log n) and how can we calculate the number of steps required to search an element from a given array using binary search without doing any calculations. It's super easy! Are you ready?

Time Complexity of Binary Search O(log n)

When we say the time complexity is log n, we actually mean log2 n, although the base of the log doesn't matter in asymptotic notations, but still to understand this better, we generally consider a base of 2.
Let's first understand what log2(n) means.
OUTPUT:
Expression: log2(n)
- - - - - - - - - - - - - - -
For n = 2:
log2(21) = 1
Output = 1
- - - - - - - - - - - - - - -
For n = 4
log2(22) = 2
Output = 2
- - - - - - - - - - - - - - -
For n = 8
log2(23) = 3
Output = 3
- - - - - - - - - - - - - - -
For n = 256
log2(28) = 8
Output = 8
- - - - - - - - - - - - - - -
For n = 2048
log2(211) = 11
Output = 11
Now that we know how log2(n) works with different values of n, it will be easier for us to relate it with the time complexity of the binary search algorithm and also to understand how we can find out the number of steps required to search any number using binary search for any value of n.

Counting the Number of Steps

As we have already seen, that with every incorrect guess, binary search cuts down the list of elements into half. So if we start with 32 elements, after first unsuccessful guess, we will be left with 16 elements.
So consider an array with 8 elements, after the first unsuccessful, binary sort will cut down the list to half, leaving behind 4 elements, then 2 elements after the second unsuccessful guess, and finally only 1 element will be left, which will either be the target or not, checking that will involve one more step. So all in all binary search needed at most 4 guesses to search the target in an array with 8 elements.
If the size of the list would have been 16, then after the first unsuccessful guess, we would have been left with 8 elements. And after that, as we know, we need atmost 4 guesses, add 1 guess to cut down the list from 16 to 8, that brings us to 5 guesses.
So we can say, as the number of elements are getting doubled, the number of guesses required to find the target increments by 1.
Seeing the pattern, right?
Generalizing this, we can say, for an array with n elements,
the number of times we can repeatedly halve, starting at n, until we get the value 1, plus one.
And guess what, in mathematics, the function log2 n means exactly same. We have already seen how the log function works above, did you notice something there?
For n = 8, the output of log2 n comes out to be 3, which means the array can be halved 3 times maximum, hence the number of steps(at most) to find the target value will be (3 + 1) = 4.

No comments: