Using Binary Search with sorted Array with duplica

Question

I've been tasked with creating a method that will print all the indices where value x is found in a sorted array.

I understand that if we just scanned through the array from 0 to N (length of array) it would have a running time of O(n) worst case. Since the array that will be passed into the method will be sorted, I'm assuming that I can take advantage of using a Binary Search since this will be O(log n). However, this only works if the array has unique values. Since the Binary Search will finish after the first "find" of a particular value. I was thinking of doing a Binary Search for finding x in the sorted array, and then checking all values before and after this index, but then if the array contained all x values, it doesn't seem like it would be that much better.

I guess what I'm asking is, is there a better way to find all the indices for a particular value in a sorted array that is better than O(n)?

public void PrintIndicesForValue42(int[] sortedArrayOfInts)
{
    // search through the sortedArrayOfInts

    // print all indices where we find the number 42. 
}

Ex: sortedArray = { 1, 13, 42, 42, 42, 77, 78 } would print: "42 was found at Indices: 2, 3, 4"

Answer 1

You will get the result in O(lg n)

public static void PrintIndicesForValue(int[] numbers, int target) {
    if (numbers == null)
        return;

    int low = 0, high = numbers.length - 1;
    // get the start index of target number
    int startIndex = -1;
    while (low <= high) {
        int mid = (high - low) / 2 + low;
        if (numbers[mid] > target) {
            high = mid - 1;
        } else if (numbers[mid] == target) {
            startIndex = mid;
            high = mid - 1;
        } else
            low = mid + 1;
    }

    // get the end index of target number
    int endIndex = -1;
    low = 0;
    high = numbers.length - 1;
    while (low <= high) {
        int mid = (high - low) / 2 + low;
        if (numbers[mid] > target) {
            high = mid - 1;
        } else if (numbers[mid] == target) {
            endIndex = mid;
            low = mid + 1;
        } else
            low = mid + 1;
    }

    if (startIndex != -1 && endIndex != -1){
        for(int i=0; i+startIndex<=endIndex;i++){
            if(i>0)
                System.out.print(',');
            System.out.print(i+startIndex);
        }
    }
}

Answer 2

I came up with the solution using binary search, only thing is to do the binary search on both the sides if the match is found.

public static void main(String[] args) {
    int a[] ={1,2,2,5,5,6,8,9,10};
    System.out.println(2+" IS AVAILABLE  AT = "+findDuplicateOfN(a, 0, a.length-1, 2));
    System.out.println(5+" IS AVAILABLE  AT = "+findDuplicateOfN(a, 0, a.length-1, 5));
    int a1[] ={2,2,2,2,2,2,2,2,2};
    System.out.println(2+" IS AVAILABLE  AT = "+findDuplicateOfN(a1, 0, a1.length-1, 2));

    int a2[] ={1,2,3,4,5,6,7,8,9};
    System.out.println(10+" IS AVAILABLE  AT = "+findDuplicateOfN(a2, 0, a2.length-1, 10));
}

public static String findDuplicateOfN(int[] a, int l, int h, int x){
    if(l>h){
        return "";
    }
    int m = (h-l)/2+l;
    if(a[m] == x){
        String matchedIndexs = ""+m;
        matchedIndexs = matchedIndexs+findDuplicateOfN(a, l, m-1, x);
        matchedIndexs = matchedIndexs+findDuplicateOfN(a, m+1, h, x);
        return matchedIndexs;
    }else if(a[m]>x){
        return findDuplicateOfN(a, l, m-1, x);
    }else{
        return findDuplicateOfN(a, m+1, h, x);
    }
}


2 IS AVAILABLE  AT = 12 
5 IS AVAILABLE  AT = 43 
2 IS AVAILABLE  AT = 410236578 
10 IS AVAILABLE  AT =

I think this is still providing the results in O(logn) complexity.

Answer 3

It is using Modified Binary Search. It will be O(LogN). Space complexity will be O(1). We are calling BinarySearchModified two times. One for finding start index of element and another for finding end index of element.

private static int BinarySearchModified(int[] input, double toSearch)
    {
        int start = 0;
        int end = input.Length - 1;

        while (start <= end)
        {
            int mid = start + (end - start)/2;
            if (toSearch < input[mid]) end = mid - 1;
            else start = mid + 1;
        }

        return start;
    }


    public static Result GetRange(int[] input, int toSearch)
    {
        if (input == null) return new Result(-1, -1);

        int low = BinarySearchModified(input, toSearch - 0.5);

        if ((low >= input.Length) || (input[low] != toSearch)) return new Result(-1, -1);

        int high = BinarySearchModified(input, toSearch + 0.5);

        return new Result(low, high - 1);
    } 

 public struct Result
    {
        public int LowIndex;
        public int HighIndex;

        public Result(int low, int high)
        {
            LowIndex = low;
            HighIndex = high;
        }
    }

Answer 4

Find_Key(int arr[], int size, int key){
int begin = 0;
int end = size - 1;
int mid = end / 2;
int res = INT_MIN;

while (begin != mid)
{
    if (arr[mid] < key)
        begin = mid;
    else
    {
        end = mid;
        if(arr[mid] == key)
            res = mid;
    }
    mid = (end + begin )/2;
}
return res;
}

Assuming the array of ints is in ascending sorted order; Returns the index of the first index of key occurrence or INT_MIN. Runs in O(lg n).

Answer 5

Well, if you actually do have a sorted array, you can do a binary search until you find one of the indexes you're looking for, and from there, the rest should be easy to find since they're all next to each-other.

once you've found your first one, than you go find all the instances before it, and then all the instances after it.

Using that method you should get roughly O(lg(n)+k) where k is the number of occurrences of the value that you're searching for.

EDIT:

And, No, you will never be able to access all k values in anything less than O(k) time.

Second edit: so that I can feel as though I'm actually contributing something useful:

Instead of just searching for the first and last occurrences of X than you can do a binary search for the first occurence and a binary search for the last occurrence. which will result in O(lg(n)) total. once you've done that, you'll know that all the between indexes also contain X(assuming that it's sorted)

You can do this by searching checking if the value is equal to x , AND checking if the value to the left(or right depending on whether you're looking for the first occurrence or the last occurrence) is equal to x.

Answer 6

Another result for log(n) binary search for leftmost target and rightmost target. This is in C++, but I think it is quite readable.

The idea is that we always end up when left = right + 1. So, to find leftmost target, if we can move right to rightmost number which is less than target, left will be at the leftmost target.

For leftmost target:

int binary_search(vector<int>& nums, int target){
    int n = nums.size();
    int left = 0, right = n - 1;

    // carry right to the greatest number which is less than target.
    while(left <= right){
        int mid = (left + right) / 2;
        if(nums[mid] < target)
            left = mid + 1;
        else
            right = mid - 1;
    }
    // when we are here, right is at the index of greatest number
    // which is less than target and since left is at the next, 
    // it is at the first target's index
    return left;
}

For the rightmost target, the idea is very similar:

int binary_search(vector<int>& nums, int target){
    while(left <= right){
        int mid = (left + right) / 2;
        // carry left to the smallest number which is greater than target.
        if(nums[mid] <= target)
            left = mid + 1;
        else
            right = mid - 1;
    }
    // when we are here, left is at the index of smallest number
    // which is greater than target and since right is at the next, 
    // it is at the first target's index
    return right;
}