Binary Search

Algorithm:

int[] arr = { 1, 3, 4, 6, 7, 9};

int target = 7

1) Make an array element in ascending or descending order.

2) Find the middle element

3) If ( ascending order) target > middle element then search in right else search in left.

if ( descending order ) target > middle element then search in left else search in right.

Example

int[] arr = {-18, -12, -4, 0, 2, 3, 4, 15, 16, 18, 22, 45, 89};

int target = 22;

check if arr is in ascending or descending order and find the target.

public static void main(String[] args) {
        int[] arr = {-18, -12, -4, 0, 2, 3, 4, 15, 16, 18, 22, 45, 89};
        int target = 22;
        int ans = binarySearch(arr, target);
        System.out.println(ans);
    }

    // return the index
    // return -1 if it does not exist
    static int binarySearch(int[] arr, int target) {
        int start = 0;
        int end = arr.length - 1;
        // find array is in ascending or descending
        boolean isAs = arr[start] < arr[end];
//        if (arr[start] < arr[end]){
//            isAs = true;
//        }
//        else {
//            isAs = false;
//        }

        while(start <= end) {
            // find the middle element
//            int mid = (start + end) / 2; // might be possible that (start + end) exceeds the range of int in java
            int mid = start + (end - start) / 2;

            if (arr[mid] == target){
                return mid;
            }
            if (isAs){
                if (target < arr[mid]) {
                    end = mid - 1;
                } else if (target > arr[mid]) {
                    start = mid + 1;
                }
            }
            else {
                if (target > arr[mid]) {
                    end = mid - 1;
                } else if (target < arr[mid]) {
                    start = mid + 1;
                }
            }

        }
        return -1;
    }

Here, the space in which we are searching is getting divided into two spaces

Time complexity

best case : O(1)

worst case : O(log n)