Order-Agnostic Binary Search - Java Solution

📘 Premium Read: Access my best content on Medium member-only articles — deep dives into Java, Spring Boot, Microservices, backend architecture, interview preparation, career advice, and industry-standard best practices.

🎓 Top 15 Udemy Courses (80-90% Discount): My Udemy Courses - Ramesh Fadatare — All my Udemy courses are real-time and project oriented courses.

▶️ Subscribe to My YouTube Channel (176K+ subscribers): Java Guides on YouTube

▶️ For AI, ChatGPT, Web, Tech, and Generative AI, subscribe to another channel: Ramesh Fadatare on YouTube

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.