Looking for good programming challenges?

Use the search below to find our solutions for selected questions!

Search for a range challenge

Sharing is caring!

Problem statement
Given a sorted array of integers, find the starting and ending position of a given target value. Your algorithm’s runtime complexity must be in the order of \mathcal{O}(log n). If the target is not found in the array, return [-1, -1]. For example, given [5, 7, 7, 8, 8, 10] and target value 8, return [3, 4].

Solution

public class SearchForARange {
    private static int[] search(int[] a, int low, int high, int target) {
        if (low > high) {
            return new int[] { -1, -1 };
        } else {
            int mid = low + (high - low) / 2;
            if (target < a[mid]) {
                // Go left
                return search(a, low, mid - 1, target);
            } else if (target > a[mid]) {
                // Go right
                return search(a, mid + 1, high, target);
            } else {
                //Go left
                int[] l = search(a, low, mid - 1, target);

                //Go right
                int[] r = search(a, mid + 1, high, target);

                int[] ans = new int[] { l[0] == -1 ? mid : l[0], r[1] == -1 ? mid : r[1] };
                return ans;
            }
        }
    }

    public static void main(String[] args) {
        int[] a = { 5, 7, 7, 8, 8, 10 };
        int[] ans = search(a, 0, a.length - 1, 8);
        System.out.println(ans[0] + ", " + ans[1]);
    }
}