Are you new to the world of programming, or computer science and want to learn about one the most efficient Searching Algorithm? Well, look no further, cause I got you covered. In this blog post, I will be introducing you to the concept of Binary Search - a technique that can greatly increase the efficiency of finding a specific value in a sorted collection of data.

What is Binary Search?

Binary search is a divide-and-conquer algorithm that is used to search for a particular value in a sorted list or array by repeatedly dividing the list in half and eliminating half of the remaining elements based on a comparison with the target value. This process is repeated until the target value is found, or until the list is narrowed down to a single element, indicating that the value is not present in the list.

Binary search is a powerful and efficient algorithm for finding values in sorted collections of data. By leveraging the divide-and-conquer approach, binary search can significantly reduce the time complexity of searching for a specific value, making it a valuable tool for programmers and computer scientists.

Binary Search Algorithm :

Since now have a little idea about the concept of Binary Search, let's make it even more clear with a step-by-step guide on the algorithm :

Imagine you have a Sorted Array/list of integers: {2, 5, 7, 10, 15, 18, 20, 25, 30}. We want to search for a target value of 18 in the above list using Binary Search.

Step 1: Initialize the Variables

Define the target value. In this case, we will be taking the value 18 as our target value to be searched.
Set two variables, a low pointer which points to the 1st element of the list and a high pointer that will be pointing to the last element.
Here the low will be pointing to value 2 and the high will be pointing to the value 30 in the list.


    public static int binarySearch(int[] arr, int target) {
        int low = 0;
        int high = arr.length - 1;

Step 2: Binary Search Loop

Now, when the low pointer is less than or equal to the high, repeat the following steps.

~ Calculate the middle index of the current search space by taking the average of the low and high pointers low + (high - low) / 2.
Compare the middle index element with the target. Now, there will be three conditions :

~ If the middle element is equal to the target value, return the index of the element.

~ If the middle element is greater than the target value, update the high pointer to mid-1 to search in the left half of the array.

~ If the middle element is lower than the target value, update low to mid + 1 to search in the right half of the array.

 while (low <= high) {
            int mid = low + (high - low) / 2; //calculate middle index
            if (arr[mid] == target) {
                return mid; // found the target value
            } else if (arr[mid] < target) {
                low = mid + 1; // update left pointer for right half
            } else {
                high = mid - 1; // update right pointer for left half
            }
        }

Step 3: Termination condition

~ If the low pointer becomes greater than the high pointer, it means the target value is not present in the list, and the search can be terminated.

Step 4: Result

If the target element is found, we will return the index of the element in the array.
If the target value is not found, we will return the value of -1 to signify the target is not present in the list. In our example, the binary search found the target value of 18 at index 5 in the list.

And that's how you implement the algorithm of Binary Search or a sorted list. Remember that binary search is most effective for searching in sorted data collections and can significantly reduce the number of comparisons needed to find a target value compared to linear search, making it a valuable algorithm for efficient searching in large datasets.

Here is a code sample for the whole process of the algorithm :

public class BinarySearch {

    public static int binarySearch(int[] arr, int target) {
        int low = 0;
        int high = arr.length - 1;

        while (low <= high) {
            int mid = low + (high - low) / 2; // calculate middle index

            if (arr[mid] == target) {
                return mid; // found the target value
            } else if (arr[mid] < target) {
                low = mid + 1; // update left pointer for right half
            } else {
                high = mid - 1; // update right pointer for left half
            }
        }

        return -1; // target value not found
    }

    public static void main(String[] args) {
        int[] arr = {2, 5, 7, 10, 15, 18, 20, 25, 30};
        int target = 18;
        int index = binarySearch(arr, target);
        if (index != -1) {
            System.out.println("Target value " + target + " found at
            index " + index);
        } else {
            System.out.println("Target value " + target + " not found            
            in the array.");
        }
    }
}

Use cases of Binary Search :

Binary search is a popular algorithm used for searching a sorted list or array of elements to find a particular value efficiently. Here are some common use cases where binary search can be applied:

Searching in a Sorted List/Array: Binary search is most commonly used for searching elements in a sorted list or array. It can quickly locate the desired element by repeatedly dividing the search space in half, resulting in a time complexity of O(log n), where n is the size of the list or array.
Searching in Databases: Binary search can be used to search for a particular record or data item in a sorted database. It can efficiently locate the record based on a key or attribute value, making it useful in database management systems and data retrieval applications.
Searching in File Systems: Binary search can be employed in file systems to search for a particular file or directory based on its name or other attributes. By leveraging the sorted nature of file system data, binary search can quickly locate the desired file or directory in large file systems.
Spell Checking: Binary search can be used in spell-checking algorithms to quickly determine if a word is present in a dictionary or a list of valid words, especially when the word list is sorted.

Variations of Binary Search :

Though the main Algorithm of Binary Search is the same for all, there exist two commonly implemented variants of Binary Search, one performed iteratively, the other, recursively. Given below are the functional codes for the implementation of the algorithm in both ways :

Iteratively :

 public static int binarySearch(int[] arr, int target) {
         int low = 0;
         int high = arr.length - 1;

         while (low <= high) {
             int mid = low + (high - low) / 2; // calculate middle index

             if (arr[mid] == target) {
                 return mid; // found the target value
             } else if (arr[mid] < target) {
                 low = mid + 1; // update left pointer for right half
             } else {
                 high = mid - 1; // update right pointer for left half
             }
         }

Recursively :

 public static int binarySearch(int[] arr, int target, int low, int high) {
         if(low > high){
             return -1;
           }
             int mid = low + (high - low) / 2;
             if (arr[mid] == target) {
                 return mid;
             } else if (arr[mid] < target) {
                 return binarySearch(arr, target, mid + 1, e);
             } else {
                 return binarySearch(arr, target, s, mid - 1);
             }
         }

Time and Space Complexity :

Since we have now seen two ways of implementing Binary Search, let's find out how optimised is our algorithm.

Iterative :

Given the size of the sorted array is n, the complexity for our code is :
```
  we can say, the array of n size divides itself in half for :- n/2 - n/4 - n/8 .. upto x times till the array is of size 1.  So, n / 2^x (2 to the power of x) = 1.
 => 2^x = n
 => x = logn(base 2)
```
The time complexity of the iterative binary search algorithm is O(log n), where 'n' is the size of the sorted array. This is because, in each iteration of the while loop, the search interval is divided in half, which reduces the size of the interval to be searched by half. Therefore, the number of iterations required to find the target element is at most log n which is highly optimised.
The space complexity of the iterative binary search algorithm is O(1), which means it uses a constant amount of extra memory. This is because it does not require any extra data structures or recursive function calls to perform the search. Instead, it uses only a few variables to keep track of the search interval and the position of the mid-element.

Recursive :

To find the Time Complexity of our recursive algorithm, we need to calculate the recurrence relation. The recurrence relation is given below :
```
 T(n) = K + T(n/2); (where k is some constant work)
 T(n/2) = T(n/4) + K;
 T(n/4) = T(n/8) + k;
 T(n/8) = T(n/16)+ k;
 .
 .
 .
 T(1) = k;
 Therefore, 
 T(n) = k * logn (Similarly to iterative approach)
      = O(logn)
```
So, our recursive algorithm also provides us with a Time complexity of O(log n).
The space complexity of the recursive binary search algorithm is O(log n) as well. This is because, in each recursive call, the function call is added to the call stack, which uses memory space. Therefore, the maximum number of recursive calls that can be made is at most log n. Thus, the space complexity of the algorithm is O(log n).

In conclusion, the recursive and the iterative approach have similar time complexities. The only place they differ is in the space optimisation since call stack functionality in recursion takes up extra space which makes our steady space complexity of O(1) to O(logn). Thus, if space is an issue, Iterative approach would be a better choice.

Binary Search vs Linear Search :

Binary search and linear search are two algorithms used for searching an element in an array. They differ in terms of their time complexity and the type of array they can search efficiently.

Binary search is an efficient algorithm for searching in a sorted array. It repeatedly divides the search interval in half until the target element is found or determined to not be present in the array. Binary search has a time complexity of O(log n). This makes it much faster than a linear search for large arrays. However, binary search requires the array to be sorted.

Linear search is a simple algorithm that checks each element of the array sequentially until the target element is found or the end of the array is reached. Linear search has a time complexity of O(n), where 'n' is the size of the array. This makes it slower than binary search for large arrays. However, linear search can be used to search any type of array, whether it is sorted or not.

In conclusion, Binary search is faster than linear search for searching in a sorted array, but it requires the array to be sorted beforehand. On the other hand, linear search can be used to search any type of array, but it is slower than binary search for large arrays. Therefore, the choice between binary search and linear search depends on the type and size of the array, as well as the specific requirements of the search operation.

Conclusion :

In conclusion, binary search is a powerful algorithm that is widely used in computer science for searching elements in a sorted array. It has a time complexity of O(log n), making it extremely efficient for large arrays. However, binary search requires the array to be sorted beforehand, and the initial sorting can take O(n log n) time. Despite this limitation, binary search is still an important tool for many real-world applications such as search engines, databases, and machine learning algorithms. By understanding the principles of binary search and how they can be implemented in various scenarios, developers and data scientists can improve the performance and efficiency of their applications.

Shounak Chakraborty's Blog