对数组进行二进制搜索，在 java 上给出了错误的索引

Question

我正在编写 不必导入 java 数组 的代码，它可以插入、删除和搜索一系列值；但是输出打印出它在调用 binSearch() 方法时没有在列表中找到值。在调用 binSearch() 之前，我已经在 main 方法中对数组进行了排序，但它仍然找不到值的索引。

我在java方面还是个初学者，所以如果你能以初学者的水平向我解释一下就太好了。

private static int[] insertElement(int index, int array[], int list[], int i) {
    int length = array.length;
    int destination[] = new int[length + 1];
    for (int j = 0; j < destination.length; j++) {
        System.arraycopy(array, 0, destination, 0, index);
        System.arraycopy(array, index, destination, index + 1, length - index);
    }
    destination[index] = list[i];
    System.out.println(list[i] + " is inserted in the list.");
    return destination;
}

private static int[] deleteElement(int index, int[] array, int list[], int i) {
    boolean[] deleteNumber = new boolean[array.length];
    int size = 0;
    for (int j = 0; j < array.length; j++) {
        if (array[j] == list[i]) {
            deleteNumber[j] = true;
            System.out.println(list[i] + " is removed from the list.");
        }
        else {
            deleteNumber[j] = false;
            size++;
        }
    }
    
    int[] newArr = new int[size];
    int in = 0;
    for (int j = 0; j < array.length; j++) {
        if (!deleteNumber[j]) {
            newArr[in++] = array[j];
        }
    }
    return newArr;
}

public static int binSearch(int[] array, int search[], int i) {
    int left = 0;
    int right = array.length - 1;
    
    if (left <= right) {
        int middle = (left + right) / 2;
        if (search[i] < array[middle]) {
            right = middle - 1;
        }
        else if (search[i] > array[middle]) {
            left = middle + 1;
        }
        else {
            System.out.print(search[i] + " is found at location ");
            return middle;
        }
    }
    return -1;
}

 public static void main(String args[]) {
    int arr[] = {2, 4, 6, 8, 9, 10, 20, 33, 44, 45, 68, 88};
    int index = 1;
    
    //insert element
    int newIndex = index - 1;
    int s[] = {3, 78, 98, 12};
    for (int i = 0; i < s.length; i++) {
        arr = insertElement(newIndex, arr, s, i);
    }
    
    //delete element
    int d[] = {20, 44, 89};
    for (int i = 0; i < d.length; i++) {
        arr = deleteElement(newIndex, arr, d, i);
    }
    
    //sort the array
    for (int i = 0; i < arr.length; i++) {
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[i] > arr[j]) {
                int swap = arr[i];
                arr[i] = arr[j];
                arr[j] = swap;
            }
        }
    }
    
    //search for element in array
    BinarySearch ob = new BinarySearch();
    int a[] = {8, 45, 88, 90};
    for (int i = 0; i < a.length; i++) {
        int result = ob.binSearch(arr, a, i);
        if (result == -1) {
            System.out.println(a[i] + " is not found in the list.");
        }
        else {
            System.out.println(result + ".");
        }
    }
    //print array
    printArray(arr);
}

Answer 1

我在我的代码中发现了错误。 binSearch() 方法应该使用 while 循环，而不是 if 循环。整个代码现在可以完美运行了。

    public static int binSearch(int[] array, int search[], int i) {
        int left = 0;
        int right = array.length - 1;
        
        while (left <= right) {
            int middle = (left + right) / 2;
            if (search[i] < array[middle]) {
                right = middle - 1;
            }
            else if (search[i] > array[middle]) {
                left = middle + 1;
            }
            else {
                System.out.print(search[i] + " is found at location ");
                return middle;
            }
        }
        return -1;
    }

Answer 2

只需将 if 子句替换为 while，因为您必须在二叉搜索树的所有级别进行搜索。变化

if (left <= right)

到

while (left <= right)

而且你的 insertElement 方法也有一个小问题。

for (int j = 0; j < destination.length; j++) {
            System.arraycopy(array, 0, destination, 0, index);
            System.arraycopy(array, index, destination, index + 1, length - index);
        }

不需要在 insertElement 方法中再次进行 for 循环，因为您已经在循环遍历需要在 main 方法中添加的数组。

对数组进行二进制搜索，在 java 上给出了错误的索引

binary search on array giving wrong index on java

java

arrays

sorting

binary-search

insertion