使用二进制搜索查找数组中的元素，使其索引等于其值

Question

我有一个升序的数组，该数组由正整数组成，并且不允许有条件重复。在数组中，我必须找到m，以便使用二进制搜索来使array [m] = m我用下面的代码：公共类主要{

public static void main(String[] args) {
    Scanner a = new Scanner(System.in);
    int n = a.nextInt();
    int arr[] = new int[n];
    for (int i = 0; i < n; i++) {
        arr[i] = a.nextInt();
    }
    int result = binarysearch(arr,n);
    if(result!=-1)
        System.out.println(result);
    else
        System.out.println("NOT_FOUND");
}

public static  int binarysearch(int[] array,int n){
int start=1,end=n;
while(start<=end){
    int mid = (start+end)/2;
    if(mid==array[mid-1])
        return mid;
    else  if(mid<array[mid-1])
        end=mid-1;
    else
        start=mid+1;
}
return -1;
}

请注意，数组是1索引而不是0索引我面临的问题是当我尝试以下情况时：array = {1,2,3,4,5}预期输出为1但是由于二进制搜索，该方法返回3作为Output。是否有任何解决方法可以绕过此类情况？

Answer 1

您的代码看起来大部分都是正确的，但是您不应该假设用户输入时已经对数组进行了排序。