Searching Algorithms

Searching algorithms is a basic, fundamental step in computing done via a step-by-step method to locate specific data among a collection of data.

What is a Search Algorithm?

According to Wikipedia- Search algorithm is-

Any algorithm which solves the search problem, namely, to retrieve information stored within some data structure, or calculated in the search space of a problem domain, either with discrete or continuous values.

They are designed to check or retrieve an element from any data structure where it is being stored. They search for a target (key) in the search space.

Types of Searching Algorithms

In this post, we are basically going to discuss two important algorithms -

Linear or Sequential Search

Binary Search

Let us discuss these two in detail with examples, code implementation, and time complexity analysis.

Linear or Sequential Search

This algorithm works by sequentially iterating through the whole array or list from one end until the target element is found. If the element is found, it returns its index, else -1.

Now let us take an example and try to understand :

arr = [2, 12, 15, 11, 7, 19, 45]

Suppose, the target element to be searched is 7.

Approach :

Start with index 0 and compare each element with the target

If the target is found to be equal to the element, return its index

If the target is not found, return -1

Code Implementation

In Java

package algorithms.searching;

public class LinearSearch {
    public static void main(String[] args) {
        int[] nums = {2, 12, 15, 11, 7, 19, 45};
        int target = 7;
        System.out.println(search(nums, target));

    }

    static int search(int[] nums, int target) {
        for (int index = 0; index < nums.length; index++) {
            if (nums[index] == target) {
                return index;
            }
        }
        return -1;
    }
}

In Python

def search(nums, target):
    for i in range(len(nums)):
        if nums[i] == target:
            return i
    return -1

if __name__ == '__main__':
    nums = [2, 12, 15, 11, 7, 19, 45]
    target = 7
    print(search(nums, target))

Time Complexity Analysis

Best Case: The best case occurs when the target element is the first element of the array. The number of comparisons, in this case, is 1. So, the time complexity is O(1).

Average Case: On average, the target element will be somewhere in the middle of the array. The number of comparisons, in this case, will be N/2. So, the time complexity will be O(N) (the constant being ignored).

Worst Case: The worst case occurs when the target element is the last element in the array or not in the array. In this case, we have to traverse the entire array, and hence the number of comparisons will be N. So, the time complexity will be O(N).

Binary Search

This type of searching algorithm is used to find the position of a specific value contained in a sorted array. The binary search algorithm works on the principle of divide & conquer and it is considered the best searching algorithm because of its faster speed to search.

Now let us take a sorted array as an example and try to understand :

arr = [2, 12, 15, 17, 27, 29, 45]

Suppose, the target element to be searched is 17.

Approach

Compare the target element with the middle element of the array.

If the target element is greater than the middle element, then the search continues in the right half.

Else if the target element is less than the middle value, the search continues in the left half.

This process is repeated until the middle element is equal to the target element, or the target element is not in the array

If the target element is found, its index is returned, else -1 is returned.

Code Implementation

In Java

package algorithms.searching;

public class BinarySearch {
    public static void main(String[] args) {
        int[] nums = {2, 12, 15, 17, 27, 29, 45};
        int target = 17;
        System.out.println(search(nums, target));
    }

    static int search(int[] nums, int target) {
        int start = 0;
        int end = nums.length - 1;

        while (start <= end) {
            int mid = start + (end - start) / 2;

            if (nums[mid] > target)
                end = mid - 1;
            else if (nums[mid] < target)
                start = mid + 1;
            else
                return mid;
        }
        return -1;
    }
}

In Python

def search(nums, target):
    start = 0
    end = len(nums)-1

    while start <= end:
        mid = start + (end-start)//2


        if nums[mid] > target:
            end = mid-1
        elif nums[mid] < target:
            start = mid+1
        else:
            return mid

    return -1


if __name__ == '__main__':
    nums = [2, 12, 15, 17, 27, 29, 45]
    target = 17
    print(search(nums, target))

Time Complexity Analysis

Best Case: The best case occurs when the target element is the middle element of the array. The number of comparisons, in this case, is 1. So, the time complexity is O(1).

Average Case: On average, the target element will be somewhere in the array. So, the time complexity will be O(logN)

Worst Case: The worst case occurs when the target element is not in the list or it is away from the middle element. So, the time complexity will be O(logN)

Calculating Time complexity:

Let say the iteration in Binary Search terminates after k iterations.

At each iteration, the array is divided by half. So let’s say the length of array at any iteration is N

At Iteration 1,

Length of array = N

At Iteration 2,

Length of array = N/2

At Iteration 3,

Length of array = (N/2)/2 = N/2^2

At Iteration k,

Length of array = N/2^k

Also, we know that after k divisions, the length of array becomes 1

Length of array = N⁄2k = 1
=> N = 2k

Applying log function on both sides:

=> log2 (N) = log2 (2k)
=> log2 (N) = k log2 (2)

As (loga (a) = 1) Therefore,

=> k = log2 (N)

Hence, the time complexity of Binary Search is log2 (N)

You can also visualise the above two algorithms using the simple tool built by Dipesh Patil - Algorithms Visualiser

Order-agnostic Binary Search

Suppose, we have to find a target element in a sorted array. Though we know that the array is sorted, we don’t know if it’s sorted in ascending or descending order.

Approach

The implementation is similar to binary search except that we need to identify whether the array is sorted in ascending order or descending order to make the decision about whether to continue the search in the left half of the array or the right half of the array.

We first compare the target with the middle element

If the array is sorted in ascending order and the target is less than the middle element OR the array is sorted in descending order and the target is greater than the middle element then we continue the search in the lower half of the array by setting end=mid-1.

Otherwise, we perform the search in the upper half of the array by setting start=mid+1

The only thing we need to do is to figure out whether the array is sorted in ascending order or descending order. We can easily find this by comparing the first and last elements of the array.

if arr[0] < arr[arr.length-1]
    array is sorted in ascending order 
else
    array is sorted in descending order

Code Implementation

In Java

package algorithms.searching;

public class OrderAgnosticBinarySearch {
    public static void main(String[] args) {
        int[] nums1 = {-1, 2, 4, 6, 7, 8, 12, 15, 19, 32, 45, 67, 99};
        int[] nums2 = {99, 67, 45, 32, 19, 15, 12, 8, 7, 6, 4, 2, -1};
        int target = -1;
        System.out.println(search(nums1, target));
        System.out.println(search(nums2, target));
    }

    static int search(int[] arr, int target) {
        int start = 0;
        int end = arr.length - 1;

        boolean isAscending = arr[start] < arr[end];

        while (start <= end) {
            int mid = start + (end - start) / 2;

            if (target == arr[mid])
                return mid;

            if (isAscending) {
                if (target < arr[mid]) {
                    end = mid - 1;
                } else {
                    start = mid + 1;
                }
            } else {
                if (target < arr[mid]) {
                    start = mid + 1;
                } else {
                    end = mid - 1;
                }
            }
        }
        return -1;
    }


}

In Python

def search(nums, target):
    start = 0
    end = len(nums)-1

    is_ascending = nums[start] < nums[end]

    while start <= end:
        mid = start + (end-start)//2

        if target == nums[mid]:
            return mid

        if is_ascending:
            if target < nums[mid]:
                end = mid-1
            else:
                start = mid+1
        else:
            if target < nums[mid]:
                start = mid+1
            else:
                end = mid-1

    return -1


if __name__ == '__main__':
    nums1 = [-1, 2, 4, 6, 7, 8, 12, 15, 19, 32, 45, 67, 99]
    nums2 = [99, 67, 45, 32, 19, 15, 12, 8, 7, 6, 4, 2, -1]
    target = -1
    print(search(nums1, target))
    print(search(nums2, target))

Time Complexity Analysis

There will be no change in the time complexity and hence will be the same as Binary Search.

Conclusion

In this blog, we discussed the two most important searching algorithms. This blog post cannot end without thanking the person who has motivated a lot of students to learn DSA, that too free of cost - Kunal Kushwaha and Community Classroom. You can also access his free DSA playlist here.
I will also soon be publishing it on GeeksforGeeks.