Problem

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

Example 1:

1
2

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

Example 2:

1
2

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

Solution

This approach is similar to binary search, but we must first determine if the array is sorted in ascending or descending order. This distinction is essential for deciding whether to search the lower or upper half of the array.

We begin with two pointers, start and end, to define our search space, initially set to 0 and n-1, respectively.

  • First, we compare the key with the middle element.
  • If the array is ascending and the key is less than the middle element, or if the array is descending and the key is greater than the middle element, we search the lower half (end = mid - 1).
  • Otherwise, the search continues in the upper half (start = mid + 1).

We can determine the sorting order by comparing the elements at the beginning and the end of the array:

1
2
3
4

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

Method 1 - Iterative Implementation

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    public int nonAgnosticBinarySearch(int[] a, int key) {
        int start = 0;
        int end = a.length - 1;
        boolean isAscending = a[start] < a[end];
        
        while (start <= end) {
            int mid = (start + end) / 2;
            if (key == a[mid]) {
                return mid;
            } else if ((isAscending && key < a[mid]) || (!isAscending && key > a[mid])) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }
        return -1;
    }
}

Method 2 - Recursive Implementation

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    public int nonAgnosticBinarySearch(int[] a, int key) {
        return binarySearchRecursive(a, 0, a.length - 1, key);
    }
    
    private 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);
        }
    }
}

Complexity

  • ⏰ Time complexity: O(log n)
  • 🧺 Space complexity: O(1)