0

Please see the below java source code for binary search implementation 

public class Main {
    public static void main(String[] args) {

        int[] x = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11};
        int y = binarySearch(x, 11);
        System.out.println(y);

    }

    public static int binarySearch(int[] arr, int value) {
        int searchedIndex = -1;
        int first = 0;
        int last = arr.length - 1;
        int mid;

        while (first <= last) {
            mid = (first + last) / 2;

            if (arr[mid] == value) {
                searchedIndex = mid;
                break;
            } else {
                if (value < arr[mid]) {
                    last = mid - 1;
                } else {
                    first = mid + 1;
                }
            }
        }

        return searchedIndex;
    }
}

int last = arr.length - 1 is -1 compulsory or not. I feel that code works fine either last = arr.length - 1. If its compulsory please explain why.

Improve this question
3
  • The array starts with 0 and ends with lengh-1. What is the problem? Commented Jul 5, 2018 at 7:38
  • Your question is a little unclear, but searching arrays you have to get the length -1 because the array indexes start at 0. So if there are 5 elements in an array, you get them by array[0], array[1] etc up to array[4]. So if you try access array.length, it will try get array[5] which doesn't exist and will throw an ArrayOutOfBoundsException. Commented Jul 5, 2018 at 7:39
  • It affect to mid calculation when there is -1.Iam not asking about array size Commented Jul 5, 2018 at 7:42

2 Answers 2

Reset to default
3

Arrays already have a method binarySearch you can just use :

int[] x = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11};
int r = Arrays.binarySearch(x, 11);
Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

Good point, but it is most likely forbidden to be used in an educational task that is given to learn basics.
I need to implement by myself rather than using java libraries.So please explain is -1 compulsory
@NipunTharuksha I tried your code and it return 10 same as my answer, please check the demo online
@deHaar I agree but the OP doesn't mention that, for that my answer was like this, also the OP can inspire from the source code of that method :)
@YCF_L this algorithm works either -1 included or not what I want to know is that is it compulsory
0

The -1 is needed for one very specific case: when you search for a value that is larger than the largest value in the array. For example, calling your function with

int y = binarySearch(x, 50);

will throw an ArrayOutOfBounds exception. That's because mid will eventually be equal to last, and without the -1, last is past the end of the array.

Improve this answer

2 Comments

Thank you very much .Good explanation
@NipunTharuksha You're welcome, glad I could help :)

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.