Last index of multiple keys using binary-search?

Question

i have multiple occurrences of a key in a sorted array, and i want to perform binary search on them, a normal binary search returns some random index for the key having multiple occurrences, where as i want the index of the last occurrence of that key.

int data[] = [1,2,3,4,4,4,4,5,5,6,6];
int key = 4;
int index = upperBoundBinarySearch(data, 0, data.length-1, key);

Index Returned = 6

Answer 1

The Java implementation in this answer finds the first occurrence of a key. There's a comment about how this could be changed to find the last occurrence, but the suggestion results in an infinite loop. The idea seems sound, though.

EDIT: After some research, I found a neat solution on The Algo Blog. Since the first found match is not necessarily the needed one, you need to keep track of the "best" match so far. When you do get a match, you store it and continue with the binary search on the right of that match (low = mid + 1).

public static int binarySearch(int[] a, int key) {
    return binarySearch(a, 0, a.length, key);
}

private static int binarySearch(int[] a, int fromIndex, int toIndex,
        int key) {
    int low = fromIndex;
    int high = toIndex - 1;
    int found = -1;

    while (low <= high) {
        int mid = (low + high) >>> 1;
        int midVal = a[mid];

        if (midVal < key) {
            low = mid + 1;
        } else if (midVal > key) {
            high = mid - 1;
        } else {
            found = mid;
            // For last occurrence:
            low = mid + 1;
            // For first occurrence:
            // high = mid - 1;
        }
    }
    return found;
}

This change keeps the O(log n) complexity. Still, the actual performance depends on the application. When the length of the array is much larger than the amount of duplications of the sought key, a linear search for the last occurrence may be faster. When there are a lot of duplications though, this modified binary search is probably preferable.

Answer 2

Presumably you want an O(log N) solution? (Otherwise you could just do a linear search.)

In C++, one possibility (out of several), is to use std::upper_bound. This will give you an iterator to the first element greater than what you asked for, so then you need to check the previous element. This is indeed O(log N).

I don't know if Java offers this a standard library method. However, the pseudocode for upper_bound is given in the link above, and should be easy enough to reimplement.

Answer 3

Well, thanks to all especially @Mattias, that algo sounds good. anyway i have done with my own, that seem me to give better result, but if some one can help me to measure out the complexity of both algos mine and @Mattias, or any one has some better solution, it welcome..... anyhow here is the solution i found for the problem,

int upperBound(int[] array,int lo, int hi, int key)
{
    int low = lo-1, high = hi;
    while (low+1 != high)
    {
        int mid = (low+high)>>>1;
        if (array[mid]> key) high=mid;
        else low=mid;
    }
    int p = low;
    if ( p >= hi || array[p] != key )
        p=-1;//no key found
    return p;
}

this is for first occurrence, i also update the same with one other similar post First occurrence in a binary search

int lowerBound(int[] array,int lo, int hi, int key)
{
    int low = lo-1, high = hi;
    while (low+1 != high)
    {
        int mid = (low+high)>>>1;
        if (array[mid]< key) low=mid;
        else high=mid;
    }
    int p = high;
    if ( p >= hi || array[p] != key )
        p=-1;//no key found
    return p;
}

Answer 4

When you find the key. instead of returning it do sequential search on the array to get the last one. This will be O(N) solution.

Answer 5

Here is a recursive version of the binary search. Tweaking this version a bit will give you the last index or the first index with zero effort and same complexity O(log-n).

The original binary search recursive version looks like this:

public static int binarySearch(List<Integer> a, int startIndex, int endIndex, int key) {
    int midIndex = (endIndex - startIndex)/2 + startIndex;
    if (a.get(midIndex) == key) // found!
        return midIndex;
    if (startIndex == endIndex || startIndex == endIndex - 1)
        return -1;
    else if (a.get(midIndex) > key) // Search in the left
        return binarySearch(a, 0, midIndex, key); 
    else if (a.get(midIndex) < key) // Search in the right
        return binarySearch(a, midIndex, endIndex, key);
    else
        return -1; // not found 
}

With a minor change of the first if statement, you can get the first index:

public static int binarySearchLowIndex(List<Integer> a, int startIndex, int endIndex, int key) {
    int midIndex = (endIndex - startIndex)/2 + startIndex;
    if (a.get(midIndex) == key && a.get(midIndex - 1) != key) // found!
        return midIndex;
    if (startIndex == endIndex || startIndex == endIndex - 1)
        return -1;
    else if (a.get(midIndex) >= key) // Search in the left
        return binarySearchLowIndex(a, 0, midIndex, key); 
    else if (a.get(midIndex) < key) // Search in the right
        return binarySearchLowIndex(a, midIndex, endIndex, key);
    else
        return -1; // not found 
}

And same goes for the last index:

public static int binarySearchHighIndex(List<Integer> a, int startIndex, int endIndex, int key) {
    int midIndex = (endIndex - startIndex)/2 + startIndex;
    if (a.get(midIndex) == key **&& a.get(midIndex + 1) != key**) // found!
        return midIndex;
    if (startIndex == endIndex || startIndex == endIndex - 1)
        return -1;
    else if (a.get(midIndex) > key) // Search in the left
        return binarySearchHighIndex(a, 0, midIndex, key); 
    else if (a.get(midIndex) <= key) // Search in the right
        return binarySearchHighIndex(a, midIndex, endIndex, key);
    else
        return -1; // not found 
}

Here are some test examples (based on Junit):

@Test
public void binarySearchTest() {
    assert(BinarySearch.binarySearch(Arrays.asList(5, 7, 7, 8, 8, 10), 0, 5, 5) == 0);
}

@Test
public void binarySearchLowIndexTest() {
    assert(BinarySearch.binarySearchLowIndex(Arrays.asList(5, 8, 8, 8, 8, 10), 0, 5, 8) == 1);
}

@Test
public void binarySearchHighIndexTest() {
    assert(BinarySearch.binarySearchHighIndex(Arrays.asList(5, 8, 8, 8, 8, 10), 0, 5, 8) == 4);
}

Answer 6

Here is my solution using recursion:

  public static int upperBoundBinarySearch(List<Integer> arr, int left, int right, int target) {

        if (left <= right) {

            int m = (int) (left + Math.floor((right - left) / 2));

            if (arr.get(m) == target) {
                if (m == arr.size() || arr.get(m + 1) != target)
                    return m;
                else
                    // Check the upper part only
                    return upperBoundBinarySearch(arr, m + 1, right, target);
            }
            // Normal Binary search
            else if (arr.get(m) < target)
                return upperBoundBinarySearch(arr, m + 1, right, target);

            else
                return upperBoundBinarySearch(arr, left, m - 1, target);
        }
        return -1;
    }

Answer 7

In the binary search you compare your key to elements of the array data[i]. To get the last matching index you should change your compare function so that it gives inequality even if key is equal to data[i] and also to data[i+1].

int upperBoundBinarySearch(int data[],int start, int end, int key) {
  while(start < end) {
    int middle = start + (end-start)/2;
    if (data[middle] == key && (middle == end || data[middle+1] != key))
      return middle;
    if (data[middle] > key)
      end = middle;
    else {
      if (start == middle)
        return start;
      start = middle;
    }
  }
  return start;
}