Order Agnostic Binary Search

The Binary Search algorithm works well on sorted arrays. but the array can be sorted in any case ie ascending and descending. most of the example provided only works on ascending-order sorted array. It Lets us understand how to find elements in order agnostic array.

In order to search in order agnostic array, first need to figure out in which order the array is sorted. One simple way is to compare the first element of the array with the second for example

1, 2, 3, 4, 5

first element 1 is smaller than second element 2, which tells the array is in ascending order sorted, but the array may contain duplicate elements as well. for example

1, 1, 1, 1, 1, 2, 3, 4, 5

here it is very hard to determine the sort order of the array by just comparing the first element and the second element. but in both cases the start and end elements will always be different, so comparing the start element with the end element will always give the correct result.

it will also take care of duplication in arrays for example

1, 1, 1, 1, 1, 1, 1, 1, 1, 1

package org.wesome.dsalgo;

public class BinarySearch {
    public static int orderAgnosticBinarySearch(int[] arr, int find) {
        return binarySearch(arr, find);
    }

    public static int binarySearch(int[] arr, int find) {
        int start = 0, end = arr.length - 1;
//        find the sort order of the array
        boolean isAsc = arr[start] < arr[end];

        while (start <= end) {
            int mid = start + (end - start) / 2;
            // If the find element is present in the middle itself
            if (arr[mid] == find) {
                return mid;
            }
//            check the sort order of the array
            if (isAsc) {
                // In ascending order sorted array, If the find is smaller than mid-element, then it can only be present in left sub-array
                if (arr[mid] > find) {
                    end = mid - 1;
                }
                // Else the element can only be present in right sub-array
                else {
                    start = mid + 1;
                }
            } else {
                // In descending order sorted array, If the element is smaller than mid-element, then it can only be present in right sub-array
                if (arr[mid] < find) {
                    end = mid - 1;
                }
                // Else the element can only be present in left sub-array
                else {
                    start = mid + 1;
                }
            }
        }
        return -1;
    }
}

package org.wesome.dsalgo;

import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;

import static org.wesome.dsalgo.BinarySearch.orderAgnosticBinarySearch;

public class BinarySearchTest {
    @Test
    void orderAgnosticBinarySearchTest1() {
        int[] arr = new int[]{1, 2, 3, 4, 5};
        int binarySearch = orderAgnosticBinarySearch(arr, 10);
        Assertions.assertEquals(-1, binarySearch);
    }

    @Test
    void orderAgnosticBinarySearchTest2() {
        int[] arr = new int[]{5, 4, 3, 2, 1};
        int binarySearch = orderAgnosticBinarySearch(arr, 10);
        Assertions.assertEquals(-1, binarySearch);
    }

    @Test
    void orderAgnosticBinarySearchTest3() {
        int[] arr = new int[]{1, 2, 3, 4, 5};
        int binarySearch = orderAgnosticBinarySearch(arr, 1);
        Assertions.assertEquals(0, binarySearch);
    }

    @Test
    void orderAgnosticBinarySearchTest4() {
        int[] arr = new int[]{5, 4, 3, 2, 1};
        int binarySearch = orderAgnosticBinarySearch(arr, 1);
        Assertions.assertEquals(4, binarySearch);
    }
}

plugins {
    id 'java'
    id "io.freefair.lombok" version "6.4.1"
}

group = 'org.wesome'
version = '0.0.1-SNAPSHOT'
sourceCompatibility = JavaVersion.VERSION_1_8

configurations {
    compileOnly {
        extendsFrom annotationProcessor
    }
}

repositories {
    mavenCentral()
}

dependencies {
    testImplementation 'org.junit.jupiter:junit-jupiter:5.6.2'
}

test {
    useJUnitPlatform()
}