First occurrence in a binary search

user_104950 0
Viewed 32803

I'm tinkering with some code and I realized something I never knew. A normal binary search will return a random index in a data set for a key that occurs more than once. How can I modify this code below to return the first occurrence? Is this something people do?

//ripped from the JDK
public static int binarySearchValue(InvertedContainer.InvertedIndex[] a, long key) {
    return bSearchVal(a, 0, a.length, key);
}

private static int bSearchVal(InvertedContainer.InvertedIndex[] a, int fromIndex,
                                 int toIndex, long key) {
    int low = fromIndex;
    int high = toIndex - 1;

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

        if (midVal < key)
            low = mid + 1;
        else if (midVal > key)
            high = mid - 1;
        else
            return mid; // key found
    }
    return (low); // key not found. return insertion point
}
binary-search binary search algorithm java
16 Answers

In this thread, you can find a full example of the binary search (recursive version), and two other versions (based on the original one) which allow you to get the first index and last index of a given key.

For your convenience I added the relevant Junit tests.

user_67925880

I think a simpler approach is storing the latest mid index where xs[mid] == key into a result variable and then keep running the binary search.

Here's the swift code:

func first<T: Comparable>(xs: [T], key: T) -> Int {
    var lo = xs.startIndex
    var hi = xs.endIndex - 1
    var res = -1
    while lo <= hi {
        let mid = lo + (hi - lo) >> 1
        if xs[mid] == key { hi = mid - 1; res = mid }
        else if xs[mid] < key { lo = mid + 1}
        else if xs[mid] > key { hi = mid - 1 }
    }

    return res
}

Also, this requires a really small change (just one line) if you were to find the last index of a key.

func last<T: Comparable>(xs: [T], key: T) -> Int {
    var lo = xs.startIndex
    var hi = xs.endIndex - 1
    var res = -1
    while lo <= hi {
        let mid = lo + (hi - lo) >> 1
        if xs[mid] == key { lo = mid + 1;  res = mid }
        else if xs[mid] < key { lo = mid + 1}
        else if xs[mid] > key { hi = mid - 1 }
    }

    return res
}
user_9641640

Try this javascript recursive solution. It's optimal in a sense that it's O(log(N))

function solve(A, e) {
  function solve (A, start, end, e, bestUntilNow) {
    if (start > end) {
      if (A[start] === e)
        return start
      return bestUntilNow
    } else {
      const mid = start + Math.floor((end - start) / 2)
      if (A[mid] === e) {
        return solve(A, start, mid - 1, e, mid)
      } else if (e < A[mid]) {
        return solve(A, start, mid - 1, e, bestUntilNow)
      } else {
        return solve(A, mid + 1, end, e, bestUntilNow)
      }
    }
  }
  return solve(A, 0, A.length, e, -1)
}
user_39752470

Given a sorted array with possibly duplicated elements like [1,1,2,2,2,2,3], the following code with time complexity O(logn) finds the indexes of the first and last occurrences of an element in the given array. This approach is based on a recursive JS Binary Search implementation by comparing with the immediately lower or immediately higher index/element after matching initially the element (as it is also suggested below). 

// Find the first occurence of the value using binary search
function binarySearchFirstOccurence(arr, left, right, value) {
  let middle = Math.floor((left+right)/2);
  if (left > right) {
    return -1;
  } else if (arr[middle] === value && (arr[middle-1] < value || middle === 0)) {
    return middle;
  } else if (arr[middle] < value) {
    return binarySearchFirstOccurence(arr, middle + 1, right, value);
  } else {
    // Going lower
    return binarySearchFirstOccurence(arr, left, middle - 1, value);
  }
}

// Find the last occurence of the value using binary search
function binarySearchLastOccurence(arr, left, right, value) {
  let middle = Math.floor((left+right)/2);
  if (left > right) {
    return -1;
  } else if (arr[middle] === value && (arr[middle+1] > value || middle === arr.length - 1)) {
    return middle;
  } else if (arr[middle] > value) {
    return binarySearchLastOccurence(arr, left, middle - 1, value);
  } else {
    // Going higher
    return binarySearchLastOccurence(arr, middle + 1, right, value);
  }
}

function sortedFrequency(arr, value) {
  let left = 0;
  let right = arr.length -1;
  let first = binarySearchFirstOccurence(arr, left, right, value);
  let last = binarySearchLastOccurence(arr, left, right, value);
  if (first === -1 && last === -1) {
    return -1;
  } else if (first === -1 && last !== -1) {
    return 1;
  } else {
    return last-first+1;
  }
}

let arr = [1,1,2,2,2,2,3];
console.log(sortedFrequency(arr, 3));

Best George

user_79655170

The solution is doing some changes in the binary search so that time complexity remains equal to O(log2n). Keep in mind that for binary search the array must be in sorted form. Following are the steps

  • Calculate the mid index
  • If the element to be searched is greater than element present at the mid index then low becomes mid + 1
  • If the element to be searched is smaller than element present at the mid index then high will become mid - 1.
  • Now lets make some changes. Suppose if two elements are same in an array so our aim is to return the first occurrence of that element. Case would be if mid index == 0 or arr[mid - 1] != arr[mid], then mid index is returned. This means that same element is not repeated and if arr[mid - 1] == arr[mid], then one will make high = mid - 1. The reason being one need to return the previous element as it is the first occurrence.

Code

def first_occurence_binary_search(arr, search_element):

n = len(arr)
low = 0
high = n - 1

while low <= high:

    mid = (low + high) // 2
    if arr[mid] > search_element:
        high = mid - 1

    elif arr[mid] < search_element:
        low = mid + 1

    else:
        if mid == 0 or arr[mid - 1] != arr[mid]:
            return mid
        else:
            high = mid - 1

return -1


array = [1, 3, 3, 3]
searching = 3
print(first_occurence_binary_search(arr=array,
                                    search_element=searching))
user_25575900
Related