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

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

契约(Contract)compareTo方法是根据数字是否大于、等于或小于给定数字返回正整数、0 或负整数。这些数字可能是 -1，也可能不是 -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;
}