创建一个二进制搜索函数，返回数组中所需元素最左边出现的索引

Question

我正在尝试创建一个二进制搜索函数，但我一直陷入循环。我仅限于使用这种磁铁。该程序已经为我提供了要搜索的元素。下面的代码创建了一个无限循环。

  public class Student < T extends Comparable <? super T >> {
public int binarySearchIter(T[] data, T key) {
    int first = 0;
    int last = data.length - 1;
    int mid, result;
    mid = (first + last) / 2;
    result = key.compareTo(data[mid]);
    while (first <= last) {
        if (result == -1) {
            return -1;
        } else if (result > 0) {
            first = mid + 1;
        } else {
            last = mid - 1;
        }
    }
    return mid;
}

Answer 1

compareTo方法的契约是return一个正整数、0或一个负整数，这取决于这个数是大于、等于还是小于给定的数。这些数字可能是也可能不是 -1，所以你不能依赖它。

因此，您应该像这样更改 while 循环：

如果结果是否定的，则键在中间元素之前所以我们更新 last 到中间索引之前。
如果结果为正，则键位于中间元素之后，因此我们将 first 更新为中间索引之后。
如果结果为零，我们刚刚找到了正确的索引。

此外，一旦更新了 first 和 last 变量，您就不会更新中间元素，因此您应该将该代码移到 while 循环中。

public static <T extends Comparable <T>> int binarySearchIter(T[] data, T key) {
    int first = 0;
    int last = data.length - 1;
    int mid, result;
    while (first <= last) {
        mid = (first + last) / 2;
        result = key.compareTo(data[mid]);
        if (result < 0) {
            last = mid - 1;
        } else if (result > 0) {
            first = mid + 1;
        } else {
            return mid;
        }
    }
    return -1;
}

Answer 2

如果这应该是二分查找，while 循环应该在 mid = (first + last) / 2;

上方开始

加上 Tunaki 的留言。

创建一个二进制搜索函数，返回数组中所需元素最左边出现的索引

Create a binary search function returning the index of the leftmost occurence of the desired element in the array

java

binary

binary-search