题解 | #二分查找#

暴力编码，使用递归不断获取起点、终点、中点下标。 其中，对于有重复数据的场景，进行了一些判断，避免取到非首次出现的位置。 import java.util.*;

public class BinarySearch { public int getPos(int[] A, int n, int val) { // 有序数组，所以数据在范围外直接返回-1 if(val<A[0] || val>A[n-1]){ return -1; } //初始二分查找的左右下标位置（因为要二分，右下标不做-1处理了，-1在结果为最后一个下标的场景会产生死循环）。 int l = 0; int r = n; return getMid(A,l,r,val); }

private int getMid(int[] A,int l,int r,int val){
    int mid = (l+r)/2;

    if(A[mid] < val){
        l = mid;
    }
    //值相等且为首位（没有更早出现的可能）或者上一位与当前位值不等（因为是有序，只要不等，那么此处就是首次出现的位置了）
    if(A[mid] == val && (mid == 0 || A[mid]!=A[mid-1])){
        return mid;
    }
     //右边的或条件不能放到当前值小于val的条件判断中（因为有序的先决条件是从小到大，首次出现又是要求往前判断，所以或语句放在这个位置）
    if(A[mid]>val || (A[mid] == val && A[mid]==A[mid-1])){
        r = mid;                        
    }
    //如果二分到左右点相邻仍未找到这个val，则说明不存在。
    if(r-l==1 && A[r]!=val && A[l]!=val){
        return -1;
    }
    return getMid(A,l,r,val);
}

}