Binary Search

Binary Search is one of the best ways to find a target element in a Sorted Array. It is one of the most widely used algorithms. It works well in ascending sorted, descending sorted, and even order-agnostic sorted arrays. but it has a limitation that it will work on sorted arrays only.
 

Binary search works or sorted array only either in ascending order or descending order.

Binary Search Algorithm works on the Divide and Conquer principle. It first divides a large sorted array data set into smaller data sets and applies the algorithm.
the Binary Search Algorithm is pretty simple and contains 4 major septs only.

1. find the middle index of the sorted array
   mid = start + (end - start) / 2
    
2. if the element on the middle index is equal to the target, this is the result
    
3. else if the element on the middle index is greater than the target, search again on the left side of the array
    
4. otherwise, search again on the right side of the array

If need to find a target element in a sorted array, find the pattern and think of a Binary Search first.

the above Binary Search Algorithm can be applied using the Iterative approach and Recursive approach as well, both results lead to the same result and time complexity of O(log N).
The major difference between the Iterative and Recursive approach of the Binary Search Algorithm is the Iterative approach has a space complexity of O(1), on the other hand, due to multiple recursion calls, the Recursive approach has a space complexity of O(log N).
so the Recursive approach is easy to implement, but the Iterative approach is more efficient.

In highly memory-efficient applications, the Iterative approach is preferred to the recursive approach programming paradigm.

Let's understand both programming paradigm

RecursiveBinary Search Algorithm

The Recursive Programming Paradigm the function makes calls to itself repeatedly and certain sets of statements are repeated unless they reach the state of recision break point and exit the call stack.

    public static int binarySearch(int[] arr, int start, int end, int find) {
        if (start > end) {
            return -1;
        }
        int mid = start + (end - start) / 2;
        if (arr[mid] == find) {
            return mid;
        }
        // If the element is present in the middle itself
        if (arr[mid] >= find) {
            // If the element is smaller than mid, then it can only be present in left sub-array
            return binarySearch(arr, start, mid - 1, find);
        }
        // Else the element can only be present in right sub-array
        else {
            return binarySearch(arr, mid + 1, end, find);
        }
    }

The Recursive Binary Search Programming Paradigm has time complexity of O(log N) and space complexity of O(log N).

Iterative Binary Search Algorithm

The Iterative Programming Paradigm also repeats a certain set of statements a number of times but uses loop statements such as for loop, while loop or do-while loop to execute the same steps.

    public static int binarySearch(int[] arr, int find) {
        int start = 0, end = arr.length - 1;
        while (start <= end) {
            int mid = start + (end - start) / 2;
            // If the element is present in the middle itself
            if (arr[mid] == find) {
                return mid;
            }
            // If the element is smaller than mid, then it can only be present in left sub-array
            else if (arr[mid] > find) {
                end = mid - 1;
            }
            // Else the element can only be present in right sub-array
            else {
                start = mid + 1;
            }
        }
        return -1;
    }

The Iterative Binary Search Programming Paradigm has time complexity of O(log N) and space complexity of O(log N)

Both The above algorithm works in ascending order sorted array only.

Best way to calculate the middle element index

the middle element index can be calculated by either (start + end)/2 and start + (end - start)/2. Let's understand the difference between both.
mid = (start + end)/2
The limit of the int value is Integer.MAX_VALUE, let's assume the value of the start and end index both is Integer.MAX_VALUE, it will result in an integer overflow error.

mid = start + (end - start)/2
the ( end - start ) will take care of the Integer.MAX_VALUE, so the integer overflow will never occur.
let's try using java

        int start = Integer.MAX_VALUE, mid = 0, end = Integer.MAX_VALUE;
        mid = (start + end) / 2;
        System.out.println("start = " + start + " end = " + end + " mid = " + mid);
        mid = (start + (end - start)) / 2;
        System.out.println("start = " + start + " end = " + end + " mid = " + mid);