Getting the first occurrence in binary search

Question

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;
        }

Eran · Accepted Answer · 2016-12-11 08:37:44Z

2

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;
    }

edited Dec 11, 2016 at 8:37

answered Dec 11, 2016 at 8:32

Eran

395k57 gold badges726 silver badges793 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Getting the first occurrence in binary search

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related