Searching Algorithms (Linear Search and Binary Search) | DSA

Searching algorithms are used to check for an element or retrieve an element from a data structure where it is stored.

The two most popular searching algorithms for arrays are:

• Linear Search
• Binary Search

Linear Search

Linear Search is the method of finding an element in an array by sequentially comparing with each element until a match is found or the whole list has been searched.

Example

Given 15 boxes kept one after the other each containing a number inside it. The boxes are indexed from 0 to 15.

You are assured that the number 42 is also kept in one of the box. You've to find the box containing the number 42.

The boxes with the indexes look like this. The numbers inside the boxes are not visible and any of these boxes can have 42 inside it.

How would you find which box contains 42?

You would use linear search by opening each box one-by-one and checking whether that box contains 42 or not.

Here,

• The best case would require checking only 1 box (1st element is 42): O(1)
• The average case would require checking half of the boxes: O(n)
• The worst case would require checking all the boxes: O(n)

Code

C++

int linearSearch (int arr[], int n, int requiredNumber) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == requiredNumber) {
            return i;
        }
    }
    
    return -1;
}

Java

static int linearSearch (int arr[], int requiredNumber) {
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == requiredNumber) {
            return i;
        }
    }

    return -1;
}

Binary Search

In the above example, what if the numbers inside the box are sorted in ascending order. Would you still check the boxes sequentially or can you optimize it?

We can have an optimization by checking the center box first and deciding whether to check left or right. This will significantly reduce the number of boxes that we have to check.

This algorithm is known as binary search.

Algorithm

• Compute middleIndex using startIndex and endIndex
• Compare required number with the middle element and return index if true
• Else if required number is lesser than middle element, recur in the left half.
• Else recur in the right half.

The base case is when number is found or no more elements to check.

Visualization

Code

C++

int binarySearchUtil (int arr[], int startIndex, int endIndex, int requiredNumber) {
    if (startIndex > endIndex) {
        return -1;
    }
    int middleIndex = (startIndex + endIndex)/2;
    if (arr[middleIndex] == requiredNumber) {
        return middleIndex;
    }
    if (arr[middleIndex] > requiredNumber) {
        return binarySearchUtil(arr, startIndex, middleIndex - 1, requiredNumber);
    }
    return binarySearchUtil(arr, middleIndex + 1, endIndex, requiredNumber);
}

int binarySearch (int arr[], int n, int requiredNumber) {
    return binarySearchUtil(arr, 0, n-1, requiredNumber);
}

Java

static int binarySearchUtil (int arr[], int startIndex, int endIndex, int requiredNumber) {
    if (startIndex > endIndex) {
        return -1;
    }
    int middleIndex = (startIndex + endIndex)/2;
    if (arr[middleIndex] == requiredNumber) {
        return middleIndex;
    }
    if (arr[middleIndex] > requiredNumber) {
        return binarySearchUtil(arr, startIndex, middleIndex - 1, requiredNumber);
    }
    return binarySearchUtil(arr, middleIndex + 1, endIndex, requiredNumber);
}

static int binarySearch (int arr[], int requiredNumber) {
    return binarySearchUtil(arr, 0, arr.length - 1, requiredNumber);
}

Complexity Analysis

• Best Case: O(1)
• Average Case: O(log n)
• Worst Case: O(log n)

Note: Binary Search can directly be applied only if the array is sorted. There are other variations of binary search which can be applied to arrays which are not exactly sorted.