Что случилось с моей реализацией алгоритма бинарного поиска?

Question

Приносим извинения за задание такого простого вопроса. Но я в тупике. Я думаю, что я реализовал решение с использованием правильного алгоритма, но по какой-то причине я получаю ошибку stackoverlow при запуске. Любая помощь?

public class BinarySearch { 
public static void main(String[] args){ 
    int[] a = new int[]{1,3,5,9,10,100,210,423,500}; 
    System.out.println(binarySearch(a,5,0,a.length-1)); 
} 
static int binarySearch(int a[], int x, int left, int right){ 
    if(left>right) 
     return -1; 
    int mid = left+right/2; 

    if(a[mid] < x){ 
     return binarySearch(a,x,mid+1,right); 
    } 
    else if (a[mid] > x){ 
     return binarySearch(a,x,left,mid-1); 
    } 
    return mid; 
} 

Answer 1

Когда вы вычисляя значение для mid, ваша сфера не является правильным.

int mid = left+right/2

против

int mid = (left+right)/2

Хотя это простое решение для вашей проблемы, вы должны также оформить предложения Петра и Laune-ые годы. Они обрабатывают целочисленные переполнения.

Если длина массива равна или близка к максимальному значению типа int в Java, вы можете столкнуться с некоторыми проблемами.