Java: Binary Search

Question

Is this an ok implementation of the binary search algorithm? It works but its an implementation I came up with and differs from my instructors. Can anyone punch a hole in it for me?

package algorithm.linearsearch;

public class BinarySearch {

public static void main(String[] args) {
    System.out.println(binarySearch(
            new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 26, 109, 1001, 1100 },
            26));

}

private static int binarySearch(int[] array, int target) {
    int p = 0;
    int r = array.length - 1;
    int q;

    while (p <= r) {
        q = (p + r) / 2;
        if (array[q] == target) {
            System.out.println("value: " + array[q]);
            return q;
        }
        if (array[q] > target) {
            r = q + 1;
        } else {
            p = q - 1;
        }

    }

    return -1;

}

}

You can also give a try to binarySearch using recursive algo. — nagendra547
– nagendra547, Commented Aug 27, 2017 at 7:29

Naman · Accepted Answer · 2017-08-27 02:45:37Z

1

Just this

if (array[q] > target) {
    r = q + 1;
} else {
    p = q - 1;
}

should be

if (array[q] > target) {
    r = q - 1; // index lower to current pivot
} else {
    p = q + 1; // index upper to current pivot
}

answered Aug 27, 2017 at 2:45

Naman

32.7k32 gold badges240 silver badges385 bronze badges

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

1 Comment

Ashutosh Jha Over a year ago

@nullpointer you missed chance of null pointer. Of all people you should not miss it as its your username :D

Ashutosh Jha · Accepted Answer · 2017-08-27 08:46:30Z

1

One thing i can say. Your program is expected to return index if found or return -1 if not found. So you don't need to print value as its input taken from user regarding which element to find.

You need a check initially if your array is null return -1 to avoid null pointer exception which will happen when you calculate length of array.

answered Aug 27, 2017 at 8:46

Ashutosh Jha

1,5432 gold badges19 silver badges28 bronze badges

Collectives™ on Stack Overflow

Java: Binary Search

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related