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

Joe
– Joe

2014-09-13 11:24:35 +00:00
Commented Sep 13, 2014 at 11:24 — Joe
– Joe, Commented Sep 13, 2014 at 11:24
How do you think first+last/2; is evaluated?

Darshan Lila
– Darshan Lila

2014-09-13 11:30:32 +00:00
Commented Sep 13, 2014 at 11:30 — Darshan Lila
– Darshan Lila, Commented Sep 13, 2014 at 11:30

M A · Accepted Answer · 2014-09-13 11:29:52Z

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, 2014 at 11:29

answered Sep 13, 2014 at 11:24

M A

73.2k14 gold badges149 silver badges182 bronze badges

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

Comments

kirti · Accepted Answer · 2014-09-13 11:32:42Z

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, 2014 at 11:32

kirti

4,6294 gold badges33 silver badges64 bronze badges

Collectives™ on Stack Overflow

Problems implementing a binary search

2 Answers 2

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related