Order-Agnostic Binary Search - Java Solution

1. Introduction

In this blog post, we'll explore the concept of Order-agnostic Binary Search. This variant of binary search is used when the sorting order of the array (ascending or descending) is not known beforehand.

Problem

Given a sorted array of numbers, find if a given number key is present in the array. The array may be sorted in ascending or descending order.

Example 1:

Input: [2, 8, 11, 19], key = 11
Output: 2

Example 2:

Input: [32, 28, 17, 9, 3], key = 9
Output: 3

2. Solution Steps

1. Determine if the array is sorted in ascending or descending order.

2. Apply binary search accordingly.

3. If the key is found, return its index; otherwise, return -1.

3. Code Program

public class Solution {

    // Main method for testing
    public static void main(String[] args) {
        int[] arr1 = {2, 8, 11, 19};
        System.out.println("Key 11 found at index: " + orderAgnosticBinarySearch(arr1, 11));

        int[] arr2 = {32, 28, 17, 9, 3};
        System.out.println("Key 9 found at index: " + orderAgnosticBinarySearch(arr2, 9));
    }

    // Method for order-agnostic binary search
    public static int orderAgnosticBinarySearch(int[] arr, int key) {
        int start = 0, end = arr.length - 1;
        boolean isAscending = arr[start] < arr[end];

        while (start <= end) {
            int mid = start + (end - start) / 2;

            if (arr[mid] == key) {
                return mid;
            }

            if (isAscending) {
                if (key < arr[mid]) {
                    end = mid - 1;
                } else {
                    start = mid + 1;
                }
            } else {
                if (key > arr[mid]) {
                    end = mid - 1;
                } else {
                    start = mid + 1;
                }
            }
        }
        return -1; // Element not found
    }
}

Output:

Key 11 found at index: 2
Key 9 found at index: 3

Explanation:

In the order-agnostic binary search, the algorithm first checks whether the given array is sorted in ascending or descending order. It then applies the standard binary search logic, modifying it based on the order of sorting. 

For the first input [2, 8, 11, 19] with key 11, the element is found at index 2. 

For the second input [32, 28, 17, 9, 3] with key 9, the element is found at index 3. 

This approach allows binary search to be applied regardless of the sorting order of the array.