Java自定义Binary Search实现异常，返回索引与原数组不符求排查

我手动推演代码上千次都没找到问题，可能是知识储备不够。我想获取目标元素在原数组中的索引，但当前代码返回的索引和原数组里的实际索引对不上，麻烦帮忙找错。

原代码 #

package _08_Arrays;

public class _04_Binary_Search {
    

public static void main(String[] args) {
    int arr[] = { 5, 3, 2, 4, 1 };
    int target = 2;
    SortArray(arr);
    System.out.print(BinarySearch(arr, target));
}

public static int BinarySearch(int[] arr, int target) {
    int s = 0; // I took int s=arr[0] which will provide inconvenience in case if I want do s++
                // or s--, it will increase the value of the element in the array by one.
    int n = arr.length;
    int e = n - 1;
    for(;s<=e;) {
        int mid=(s+e)/2;
        if(arr[mid]>target) {
            e=mid-1;
        } else if(arr[mid]<target) {
            s=mid+1;
        } else {
            return mid;
        }
    }
    return -1;
}

public static void SortArray(int[] arr) {
    // TODO Auto-generated method stub
    int idx=-1;
    int sort=0;
    for(int j=0;j<arr.length;j++) {
        int min=Integer.MAX_VALUE;
        for(int i=sort;i<arr.length;i++) {
            if(arr[i]<min) {
                min=arr[i];
                idx=i;
            }
        }
        int temp=arr[sort];
        arr[sort]=min;
        arr[idx]=temp;
        sort++;
        }
}

问题根源 #

你调用SortArray(arr)时直接修改了原数组的元素顺序，原数组{5,3,2,4,1}被排序成{1,2,3,4,5}，之后的二分查找是在排序后的数组上执行的，返回的自然是排序后数组的索引，和原数组的索引完全不匹配。

比如目标元素2在原数组的索引是2，但排序后它的位置变成了索引1，所以代码返回1，和你想要的原索引不一致。

解决方案 #

根据你的需求，分两种情况处理：

情况1：必须用二分查找（需要有序数组），同时保留原索引

不要直接修改原数组，而是创建一个能关联元素值和原索引的结构，排序这个结构后再做二分查找，找到后返回原索引。示例代码如下：

package _08_Arrays;

import java.util.Arrays;

public class _04_Binary_Search {
    public static void main(String[] args) {
        int arr[] = {5, 3, 2, 4, 1};
        int target = 2;
        
        // 创建二维数组，每个元素存储[元素值, 原数组索引]
        int[][] arrWithIndex = new int[arr.length][2];
        for (int i = 0; i < arr.length; i++) {
            arrWithIndex[i][0] = arr[i];
            arrWithIndex[i][1] = i;
        }
        
        // 按元素值从小到大排序
        Arrays.sort(arrWithIndex, (a, b) -> Integer.compare(a[0], b[0]));
        
        // 二分查找并返回原索引
        System.out.print(BinarySearchWithOriginalIndex(arrWithIndex, target));
    }

    public static int BinarySearchWithOriginalIndex(int[][] arrWithIndex, int target) {
        int s = 0;
        int e = arrWithIndex.length - 1;
        while (s <= e) {
            int mid = (s + e) / 2;
            if (arrWithIndex[mid][0] > target) {
                e = mid - 1;
            } else if (arrWithIndex[mid][0] < target) {
                s = mid + 1;
            } else {
                return arrWithIndex[mid][1]; // 返回原数组的索引
            }
        }
        return -1;
    }
}

情况2：不需要二分查找，仅需获取原数组中目标元素的索引

直接遍历原数组即可，不需要排序，这样不会改变元素位置，直接返回原索引：

package _08_Arrays;

public class _04_Binary_Search {
    public static void main(String[] args) {
        int arr[] = {5, 3, 2, 4, 1};
        int target = 2;
        System.out.print(findOriginalIndex(arr, target));
    }

    public static int findOriginalIndex(int[] arr, int target) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == target) {
                return i;
            }
        }
        return -1; // 未找到目标元素返回-1
    }
}

内容的提问来源于stack exchange，提问作者Shruti Kumari