Mastering Binary Search: Your Ultimate Guide to Efficient Searching | Program Feed | Vinayak Sutar

   

    Searching simply means finding whether an element within a collection exists or not. It may be an array, tree, or graph. In this blog, we will study how to find out whether an element exists within an array using the binary search method.

    Let's understand how binary search works. Suppose we have an array of data-type integers. To perform a binary search it is a must that the array should be sorted. With that, we can perform a binary search. Suppose we have an array as follows:

    Let's say that our target element in this array is 25. So now we have to check whether 25 exists or not. For that, we have to create three variables startIndex, lastIndex, and midIndex. By default, the first value of startIndex will be the starting index of the array which is 0 and lastIndex will be the index of the last element of the array which is 6 in this case. The midIndex will be calculated by the formula (startIndex + lastIndex / 2) which is 4 in this case.

Iteration 1

startIndex = 0

lastIndex = 6

midIndex = (startIndex + lastIndex) / 2 = (0 + 6) / 2 = 3

    In the first iteration, we have 3 as a midIndex. So will check whether the target element exists in the midIndex or not.  If it exists then we can say that the target element exists in the given array, but in this case, as we can see at index 3 we have 17 which is not the target element that we want. 

    Then we have to check whether the element which we have found at the midIndex which is 17 is greater or smaller than the target element. So 25 is of course greater than 17. As we know the given array is sorted, so we can completely ignore the first half of the array. For that, we have to update startIndex to midIndex which is 3.

Iteration 2

    So now we have startIndex at 3 and lastIndex at 6. As per the formula we have to find the middle index of the new shrunk array.

startIndex = 3

lastIndex = 6

midIndex = (startIndex + lastIndex) / 2 = (3 + 6) / 2 = 4.5 ~ 4

    Here we got 4 as our midIndex. At index 4 there is 22 which is not equal to our target which is 25. So again we have to repeat this step again.

Iteration 3

    In the previous iteration, we got 22 at the midIndex which is our target element. So now we have to update our midIndex to startIndex. 

startIndex = 4

lastIndex = 6

midIndex = (startIndex + lastIndex) / 2 = (4 + 6) / 2 = 5

    So now we have 5 as midIndex which has 25 which is also equal to the target element. So now we have the target element that we are trying to search. 

    

    This is how binary search works. Hope you understood the binary search. If you have any doubts then feel free to ask in the comment section. Meet you in the new blog with the new learning, Till then happy coding!

import java.util.Scanner;

public class BinarySearch {
    public static void main(String[] args) {
        int[] arr = { 2, 5, 9, 14, 18, 22, 27 };
        Scanner scanner = new Scanner(System.in);
        int target;
        int start = 0;
        int last = arr.length;
        int mid = (start + last) / 2;
        boolean found = false;
        System.out.print("Enter target element : ");
        target = scanner.nextInt();
        while (last > start && mid != start && mid != last) {
            if (arr[mid] == target) {
                found = true;
                break;
            } else {
                if (target > arr[mid]) {
                    start = mid;
                } else {
                    last = mid;
                }

                mid = (start + last) / 2;
            }
        }

        if (found) {
            System.err.print("Element found at index " + mid);
        } else {
            System.out.println("Target element does not exist in the array");
        }
    }
}