Как отлаживать проблемы с моей функцией двоичного поиска в Java?

Question

Прежде всего, мне нужно рассчитать, когда поиск числа больше, чем число «приземлилось». (меньше, и я могу просто использовать/2, но я не знаю, что делать, когда это наоборот, поскольку я использую int, а не double.)

Во-вторых, я получаю ошибку за пределы, Знать причину.

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; 
      } 
     } 
    } 
} 

Answer 1

Алгоритм двоичного поиска не совсем так, как вы его написали. Вот первый результат от Google: http://algs4.cs.princeton.edu/11model/BinarySearch.java.html

Answer 2

Вот код модернизирован с правильным бинарным алгоритмом поиска, взятым из ссылки, которая упоминается Джордж.

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); 
    } 
} 

Алгоритм сохраняет вдвое отсортированный массив чисел в зависимости от того, число в mid больше или меньше, чем значение входного lt. Кроме того, вы должны предоставить некоторую обработку ошибок, если пользовательский ввод не найден в отсортированном массиве.