Binary search of the first occurrence k

Question

I have code that looks for a sorted array and returns the index of the first occurrence of k. I am wondering if it is possible to write this code with

while(left<right) 

instead

while(left<=right)

Here is the complete 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 to know when to use the left, less than or equal to the right, or just use the left corner less than the right.

Answer 1

Based 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 cannot stop when you find the corresponding element. Your search should look like this (of course, this assumes 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;
}

, . , valueToFind, , , , ,.

.

Answer 2

, .

, , .. {0}, 0.

left == right, while(left<right), searchFirstOfK -1.

---

. , while(left<right), Matt Timmermans , .

Matt (OP - Let call it Normal Binary) Matt Timmermans ( ) , 0 5000000:

Answer 3

. , . , , .

while(left+1<right)
{
   m = (left+right)/2;
   if(check condition is true)
      left = m;
   else
      right =  m;
}

, , , . , . , .

The above initialization will give you the biggest condition satisfying the element.

By changing the initialization, you can get many elements (for example, a small condition that satisfies the elements).