java - 如何通过二分查找获取数组中的最后一个字符

Question

我的老师编写了一个算法来查找数组中的数字。我尝试将其转换为char。

如果我搜索数组的第一个 char ，它会起作用，但如果我尝试在同一数组中查找最后一个 char ，它会给我 0 或意外的数字(例如 100+，当数组类似于 4 个 char 时)。

代码如下:

int myIndex = binarySearch(sentence , word[0], 0, sentence.length -1);

char [] sentence = {'s','t','a','c','k','o','v','e','r','f','l','o','w'};
char [] word = {'o','v','e','r'};

static int binarySearch(char [] arr, char x, int l, int r){
    if(r<l){
        return 0;
    }

    int m = l+(r-l)/2;
    if(arr[m] == x){
        return m;
    }
    if(arr[m] < x){
        return binarySearch(arr, x, m+1, r);
    }
    return binarySearch(arr, x, l, m-1);
}

如果我在 word 数组中搜索第一个字母，它工作正常，但如果我在 word 数组中搜索最后一个字母，它就会崩溃。

Answer 1

您正在对未排序的字符输入数组 arr 使用二分搜索。因此，您必须首先对数组进行排序或对未排序的数组使用线性搜索。