Problems implementing a binary search

Question

I'm feeling very very stupid because I've solved much harder stuff than this. This is supposed to be an implementation of ordered binary search. Whenever I trace the 12, a stackoverflow error pops up. Any help please?

public class binarySearch {        
    public static void main(String[] args) {
        int[] arr = { 1, 5, 6, 8, 12, 88 };
        System.out.println(binaryHelper(0, arr.length - 1, 12, arr));
    }

    public static int binaryHelper(int first, int last, int target, int[] arr) {
        if(first > last) return -1;
        else {
            int mid = first + last / 2;
            if(arr[mid] == target) return mid;
            else if(arr[mid] > target) return binaryHelper(first, mid - 1, target, arr);
            else return binaryHelper(mid + 1, last, target, arr);
        }
    }
}

possible duplicate of [Java BinarySearch](http://stackoverflow.com/questions/12517764/java-binarysearch) — Joe, Sep 13 '14 at 11:24

M A · Accepted Answer · 2014-09-13T11:29:52.147

2

This is due to the precedence order of your operators in your mid variable computation. It should be computed as:

int mid = (first + last) / 2;

instead of

int mid = first+last/2;

edited Sep 13 '14 at 11:29

answered Sep 13 '14 at 11:24

M A

71,713
13
134
174

score 1 · Answer 2 · answered Sep 13 '14 at 11:32

1

Error is here:

 int mid = first+last/2;

this means mid is equal to first + last dividied by 2 which is wrong

so it should be like

int mid = (first+last)/2;

answered Sep 13 '14 at 11:32

kirti

4,499
4
31
60

Problems implementing a binary search

2 Answers2