java - Java最左边的二进制搜索

我正在尝试修改递归二进制搜索函数，以便在数组包含该元素的倍数的情况下，它将找到该元素的最左侧索引。

import java.util.*;
import java.util.Arrays;
import java.io.File;
import java.io.IOException;

public class LeftmostBinarySearch {

    private static int myBinarySearch(int key, int[] a, int lo, int hi) {
    if (lo > hi) {
        return -1;
    }
    int mid = lo + (hi - lo) / 2;
    if (key < a[mid]) {
        return myBinarySearch(key, a, lo, mid - 1);
    } else if (key > a[mid]) {
        return myBinarySearch(key, a, mid + 1, hi);
    } else {
        return mid;
    }
}

    public static int myBinarySearch(int key, int[] a) {
    return myBinarySearch(key, a, 0, a.length - 1);
}

    public static void main(String[] args) throws IOException {
        String fileName = args[0] + ".txt";
        System.out.println(fileName);
        Scanner scanner = new Scanner(new File(fileName));
        int[] data = new int[7];
        int i = 0;
        int j = 0;

        while (scanner.hasNextInt()) {
            data[i] = scanner.nextInt();
            i++;
        }
        Arrays.sort(data);
        System.out.format("%2s%2s%2s%2s%2s%2s%2s%2s%2s%2s%2s%2s%2s", " 0",
                "  ", " 1", "  ", " 2", "  ", " 3", "  ", " 4", "  ", " 5", "  ", " 6\n");
        System.out.format("%2s%2s%2s%2s%2s%2s%2s%2s%2s%2s%2s%2s%2s", data[j],
                "  ", data[j + 1], "  ", data[j + 2], "  ", data[j + 3], "  ",
                data[j + 4], " ", data[j + 5], "  ", data[j + 6] + "\n");

        int input = new Scanner(System.in).nextInt();

        while ((Integer) input != null) {
            int key = input;
            System.out.println(data[0]);
            if (myBinarySearch(key, data) != -1) {
                System.out.println(input + " found: "
                        + myBinarySearch(key, data));
            }
            input = new Scanner(System.in).nextInt();
        }
    }
}

我从中得到的输出是：

C:\Users\Shirley\algs4>java LeftmostBinarySearch mydata
 0   1   2   3   4   5   6
10  20  20  30  40  40  40
10
10 found: 0
20
20 found: 1
30
30 found: 3
40
40 found: 5

我试过更改中值到（hi + lo-1）/ 2的计算方式，它适用于40，给出索引3，但适用于20，给出索引2。

最佳答案

问题出在最后一行：

else return mid;

您的列表包含重复项，因此mid可能不是最左边的匹配项。因此，请尝试：

else {
  while(--mid>=0) {
    if (a[mid]!=key) break;
  }
  return mid+1;
}