Binary search for first occurrence of k

Question

I have code that searches a sorted array and returns the index of the first occurrence of k. I am wondering whether its possible to write this code using

while(left<right) 

instead of

while(left<=right)

Here is the full code:

public static int searchFirstOfK(List<Integer> A, int k) {
   int left = 0, right = A.size() - 1, result = -1;
   // A.subList(left, right + 1) is the candidate set.
   while (left <= right) {
      int mid = left + ((right - left) / 2);
      if (A.get(mid) > k) {
         right = mid - 1;
      } else if (A.get(mid) == k) {
         result = mid;
         // Nothing to the right of mid can be the first occurrence of k.
         right = mid - 1;
      } else { // A.get(mid) < k
         left = mid + 1;
      }
   }
   return result;
}

How do I know when to use left is less than or equal to right, or just use left is less than right.

Answer 1

Building on this answer to another binary search question: How can I simplify this working Binary Search code in C?

If you want to find the position of the first occurrence, you can't stop when you find a matching element. Your search should look like this (of course this assumes that the list is sorted):

int findFirst(List<Integer> list, int valueToFind)
{
    int pos=0;
    int limit=list.size();
    while(pos<limit)
    {
        int testpos = pos+((limit-pos)>>1);

        if (list.get(testpos)<valueToFind)
            pos=testpos+1;
        else
            limit=testpos;
    }
    if (pos < list.size() && list.get(pos)==valueToFind)
        return pos;
    else
        return -1;
}

Note that we only need to do one comparison per iteration. The binary search finds the unique position where all the preceding elements are less than valueToFind and all the following elements are greater or equal, and then it checks to see if the value you're looking for is actually there.

The linked answer highlights several advantages of writing a binary search this way.