How to implement a recursive binary search algorithm?

Question

I need to implement a recursive binary search algorithm for an integer array sorted in ascending order (i.e 1,2,3,4...).

The array I have contains the following numbers:

0 0 0 0 0 0 0 1 2 2 3 3 3 3 5 6 7 7 7 9

However, my current implementation of binary search only finds the numbers to the right of 3. For some reason, it doesn't find 9, 7, 6, and 5.

below is my code:

private int srchHelper(int[] array, int first, int last, int x) {
    if (first > last) return - 1;
    int mid = (first + last) / 2;
    if (array[mid] == x) {
        return mid;
    }
    if (array[mid] < x) {
        return srchHelper(array, (mid + 1), last, x);
    }
    else return srchHelper(array, (mid - 1), last, x);
}

I saw this question yesterday, and about 3 people commented with the correct answer. — Paul Boddington, Mar 21 '16 at 22:11
If you want to go left, wouldn't your `int first` be the left most option (`first`), and not `mid`, and wouldn't last be `mid` and not `last` on the very first go? — Ceelos, Mar 21 '16 at 22:11
@PaulBoddington do you have the link to that question, to mark this as a duplicate? — Mike 'Pomax' Kamermans, Mar 21 '16 at 22:22
This one? http://stackoverflow.com/questions/19012677/how-to-use-recursion-in-creating-a-binary-search-algorithm — fabriziocucci, Mar 21 '16 at 22:24

score 0 · Answer 1 · answered Mar 21 '16 at 22:37

0

Make sure you're clear about what the algorithm does, and then take a good long look at your recursive calls.

answered Mar 21 '16 at 22:37

Edward Peters

3,623
2
16
39

How to implement a recursive binary search algorithm?

1 Answers1