Binary Search (Recursively) in Java

#java #binarysearch #algorithms

Create a method `binarySearch()` inside `BinarySearch` class

public class BinarySearch {

    int binarySearch(int arr[], int left, int right, int key) {
       //todo
    }
}

    int binarySearch(int arr[], int left, int right, int key) {
       if (right >= left) {
            int middle = left + (right - 1) / 2;

            //todo
        }
    }

    int binarySearch(int arr[], int left, int right, int key) {
       if (right >= left) {
            int middle = left + (right - 1) / 2;

            if (arr[middle] == key) {
                return middle;
            }
            //todo
        }
    }

    int binarySearch(int arr[], int left, int right, int key) {
       if (right >= left) {
            int middle = left + (right - 1) / 2;

            if (arr[middle] == key) {
                return middle;
            }
            if (arr[middle] > key) {
                return binarySearch(arr, left, middle - 1, key);
            }
            //todo
        }
    }

    int binarySearch(int arr[], int left, int right, int key) {
       if (right >= left) {
            int middle = left + (right - 1) / 2;

            if (arr[middle] == key) {
                return middle;
            }
            if (arr[middle] > key) {
                return binarySearch(arr, left, middle - 1, key);
            }
            return binarySearch(arr, middle + 1, right, key);

            //todo
       }
    }

    int binarySearch(int arr[], int left, int right, int key) {
       if (right >= left) {
            int middle = left + (right - 1) / 2;

            if (arr[middle] == key) {
                return middle;
            }
            if (arr[middle] > key) {
                return binarySearch(arr, left, middle - 1, key);
            }
            return binarySearch(arr, middle + 1, right, key);
       }
        return -1;
    }

`main` method...

    public static void main(String[] args) throws Exception {
        int arr[] = { 0, 5, 7, 12, 45, 53 };
        int key = -3;
        BinarySearch bs = new BinarySearch();

        int index = bs.binarySearch(arr, 0, arr.length - 1, key);

        if (index == -1) {
            System.out.println("" + key + " not found");
        } else {
            System.out.println("" + key + " found at " + index);
        }

    }

Final Code...

public class BinarySearch {

    int binarySearch(int arr[], int left, int right, int key) {
        if (right >= left) {
            int middle = left + (right - 1) / 2;

            if (arr[middle] == key) {
                return middle;
            }
            if (arr[middle] > key) {
                return binarySearch(arr, left, middle - 1, key);
            }

            return binarySearch(arr, middle + 1, right, key);
        }

        return -1;
    }

    public static void main(String[] args) throws Exception {
        int arr[] = { 0, 5, 7, 12, 45, 53 };
        int key = -3;
        BinarySearch bs = new BinarySearch();

        int index = bs.binarySearch(arr, 0, arr.length - 1, key);

        if (index == -1) {
            System.out.println("" + key + " not found");
        } else {
            System.out.println("" + key + " found at " + index);
        }

    }
}