Introduction to Algorithms: Linear vs. Binary Search

Algorithms rule the world. This is not a drill. It is a universal truth. We are surrounded by them in every step and yet we're oblivious to its importance.

Algorithms are solutions. It is a solution to a problem or too many problems. Algorithms are finite number of steps that solves a given problem. Solutions are independent of the machines.

Programming has changed over the years. It has gone through a rapid evolution. Yet some of the basic principles have remained constant. Primarily, the science of computing is to solve the problems using computers. A problem is computable if an algorithms exists for solving it. Hence the word computable for the problems that can be solved using algorithms.

Programming is a different paradigm used to represent solutions to the problems in computer science. Algorithms have a stepwise process and input data to provide intended solution to a problem. And programming languages are created to provide a set of notations to represent these processes and their data in the form of a program.

In this series of articles, we will be familiar with various algorithms and their data structures, time and space complexity, problem statement with the solution and more in-depth analytical explanation. We're going to learn some of the most common and advanced algorithms that are so simple and yet solve most of the basic to advanced problems in different fields like technology, engineering, finance, business and more.

An example of an unsorted array of 10 elements could be

[4, 8, 10, 1, 3, 6, 9, 7, 2, 5]

If you sort this array in either of the ascending or descending order then the sorted array will be

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10] or [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]

Linear Search

• Linear search is a searching method in a linear fashion i.e. step wise; one step at a time and moving onto next one.
• It is the most common algorithm or searching techniques used in our daily lives. We count sequentially or in a one after another approach to find a target element.
• For example, looking for your cereal in an aisle of a shopping mall or finding a dress in your wardrobe.

Alias: Sequential Search

Time Complexity:

O(n) is the worst case

O(1) is the best case

Space Complexity:

O(1)

Given a random array of n elements, here is a linear search method to find the target element.

Steps:

1. Start from the first element of the array.
2. Compare the target with current element of the array.
3. If found, return the index of the element.
4. Else iterate the step 2.
5. Return -1 at the end of array.

Pseudocode:

linearSearch (item, array){
	for (i=0; i < lengthOf(array); i++)
    	if (array(i) == item){
        	return i
        }
    return -1
}

Binary Search

• Binary Search is a search algorithm. It is a method used to search items in a sorted array using either of two methods: Iteration or Recursion.
• The iterative way is to execute the main search method number of times until the item is not found. On contrary, the recursive way is to formulate a recursive callback to the main search method passing new values at each loop checking the condition to either run or stop the search further. However, both ways yield the same predictable output given the right conditions.
• Here the main concept is to use the divide and conquer rule; divide the total set by half each time to search for an item until the array size is 0.

Alias: Logarithmic search

Time Complexity:

O(log n) is worst case

O(1) is best case

Space Complexity:

O(1) is an iterative approach

O(1) for recursive approach if tail call optimization is used

Steps:

1. Start indexing at 0. Repeat until sizeOf (array) = 0.
2. Set Lower index i.e. low=0 and Higher index = length of array i.e. high=lengthOf(array)
3. Pick the element in the middle index from the given array i.e. (low + high) / 2 = midpoint index
4. If the target element is equal to the current element. Return index. i.e. midpoint element = target element
5. Else if the target element is greater then switch to right side (2nd half) of array i.e. low=midpoint+1 and high=lengthOf(array)
6. Else if the target element is smaller then switch to left side (1st half) of array i.e. low=0 and high=midpoint-1
7. Calculate the new midpoint and keep finding target element with the current index element iteratively.
8. Return -1 if not found in the array.

Pseudocode:

var sortedArray = array[]
var targetElement = x

binarySearch{
    initialize low = 0, high = lengthOf(array) - 1
    
    while low >= high{
    	mid = (low + high) / 2
        if array[mid] = x
        	return indexOf(mid). Stop
        else if mid[a] > x
        	low = mid + 1
        else
        	high = mid - 1
    }
    
    return -1
}