How to debug issues with my binary search function in Java?

Question

First of all I need a calculation for when the looked for number is greater then the number "landed" on. (less and I can just use /2 but I don't know what to do when it's the other way since I use int and not double.)

Secondly I'm getting an out of bounds error which I don't know the cause of.

import java.util.ArrayList;
import java.util.Arrays;
import javax.swing.JOptionPane;

public class BinärSökning {
    public static void main(String[] args){

        ArrayList<Integer> listA = new ArrayList<Integer>();
        Integer[] otherList = new Integer[] {1,2,3,4,5,6,7,8,9,10};
        listA.addAll(Arrays.asList(otherList));

        String lts = JOptionPane.showInputDialog("Which number between 1 and 10 are you looking for? ");
        int lt = Integer.parseInt(lts);

        int s = listA.size()/2;

        while(true){
            if(lt==listA.get(s)){

                System.out.println("Number found in position " + s);

            }if(lt<listA.get(s)){

                s = ???;

            }else{

                s = s/2;
            }
        }
    }
}

GC-Java · Accepted Answer · 2015-03-30 00:18:12Z

1

The algorithm for binary search is not quite the way your wrote it. Here's the first result from google: http://algs4.cs.princeton.edu/11model/BinarySearch.java.html

answered Mar 30, 2015 at 0:18

GC-Java

18711 bronze badges

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

Comments

Tim Biegeleisen · Accepted Answer · 2015-03-30 00:32:02Z

0

Here is your code retrofitted with the correct binary search algorithm taken from the link which George mentioned.

int lo = 0;
int hi = listA.size - 1;
while (lo <= hi) {
    int mid = lo + (hi - lo) / 2;

    if (lt < listA.get(mid)) {
        hi = mid - 1;
    } else if (lt > listA.get(mid)) {
        lo = mid + 1;
    } else {
        System.out.println("Number found in position ", mid);
    }
}

The algorithm keeps halving the sorted array of numbers depending on whether the number at mid is greater or less than the input value lt. Also, you should provide some error handling in case the user input cannot be found in the sorted array.

answered Mar 30, 2015 at 0:32

Tim Biegeleisen

526k32 gold badges324 silver badges399 bronze badges

Collectives™ on Stack Overflow

How to debug issues with my binary search function in Java?

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related