CODEWITHSUNDEEP
java
user2650277
user2650277

Reputation: 6739

Getting the first occurrence in binary search

I am trying to get the first occurrence of the number 5.The answer should be 2 in this case but i am getting 3 here.

public static void main(String[] args) {
            int A[] = {1, 3, 5, 5, 5, 17, 20};
            int index = BinarySearch(A, 5);
            System.out.println(index);
        }

        public static int BinarySearch(int[] A, int x) {
            int low = 0;
            int high = A.length - 1;

            while (low <= high) {
                //(low + high) / 2
                int mid = low + (high-low)/2; // more optimal -> low + (high-low)/2 (avoid integer overflow)
                if (x == A[mid]) {
                    return mid;
                } else if (x < A[mid]) {
                    high = mid - 1;
                } else {
                    low = mid + 1;
                }
            }
            return -1;
        }

Upvotes: 1

Views: 1865

Answers (1)

Eran
Eran

Reputation: 393936

When you find the value you are looking for, you return the mid index immediately without checking if there are smaller indices having the same value.

You have to continue searching :

    public static int BinarySearch(int[] A, int x) {
      int low = 0;
      int high = A.length - 1;
      int mid = -1;
      while (low <= high) {
        mid = low + (high-low)/2;
        if (x <= A[mid]) { // this ensures you keep searching for the first index having
                           // the number you are looking for
                           //
                           // changing x <= A[mid] to x < A[mid] will give you the
                           // last index having the number you are looking for instead
          high = mid - 1;
        } else {
          low = mid + 1;
        }
      }
      if (mid >= 0 && x == A[mid]) {
        return mid;
      }
      return -1;
    }

Upvotes: 2

Related Questions