Binary Search

Order-agnostic Binary Search

Rajeev SinghAlgorithms1 mins read

Order-agnostic Binary Search

Given a sorted array of numbers, find if a given number key is present in the array. Though we know that the array is sorted, we don’t know if it’s 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

Order-agnostic Binary Search Implementation

The implementation is similar to binary search except that We need to identify whether the array is sorted in ascending order or descending order to make the decision about whether to continue the search in the lower half of the array or the upper half of the array.

Just like binary search, we initialize two variables start and end that define our search space. Initially start=0 and end=n-1.

  • We first compare the key with the middle element
  • If the array is sorted in ascending order and the key is less than the middle element OR the array is sorted in descending order and the key is greater then the middle element then we continue the search in the lower half of the array by setting end=mid-1.
  • Otherwise, we perform the search in the upper half of the array by setting low=mid+1

We can easily figure out the sorting order by comparing a[start] and a[end] .

if a[start] < a[end]
    array is sorted in ascending order 
else
    array is sorted in descending order

Iterative Implementation

import java.util.Scanner;

class BinarySearchOrderNotKnown {
    private static int binarySearch(int[] a, int key) {
        int start = 0;
        int end = a.length - 1;

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

            if (key == a[mid]) {
                return mid;
            } else if ((a[start] < a[end] && key < a[mid]) || (a[start] > a[end] && key > a[mid])) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }

        return -1;
    }

    public static void main(String[] args) {
        Scanner keyboard = new Scanner(System.in);
        int n = keyboard.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = keyboard.nextInt();
        }
        int key = keyboard.nextInt();
        keyboard.close();

        System.out.printf("BinarySearch(%d) = %d%n", key, binarySearchRecursive(a, 0, n - 1, key));
    }
}

Recursive Implementation

import java.util.Scanner;

class BinarySearchOrderNotKnown {
    private static int binarySearchRecursive(int[] a, int start, int end, int key) {
        if (start > end) {
            return -1;
        }
        int mid = (start + end) / 2;

        if (key == a[mid]) {
            return mid;
        } else if ((a[start] < a[end] && key < a[mid]) || (a[start] > a[end] && key > a[mid])) {
            return binarySearchRecursive(a, start, mid - 1, key);
        } else {
            return binarySearchRecursive(a, mid + 1, end, key);
        }
    }

    public static void main(String[] args) {
        Scanner keyboard = new Scanner(System.in);
        int n = keyboard.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = keyboard.nextInt();
        }
        int key = keyboard.nextInt();
        keyboard.close();

        System.out.printf("BinarySearch(%d) = %d%n", key, binarySearchRecursive(a, 0, n - 1, key));
    }
}