我的二进制搜索算法实现有什么问题

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

虽然这是你的问题的一个简单的解决方案，但你也应该看看Peter和laue的建议。它们都处理整数溢出。

如果数组的长度等于或接近Java中int数据类型的最大值，您可能会遇到一些问题。