二分法查找第一个满足条件的项

public class BinSearch1st {
    Random random = new Random();
    
    /**
     * 二分查找，找到s的下标，如果没有返回-1
     * @param arr
     * @param s
     * @return
     */
    public int bsearch(int[] arr, int s) {
        int left = 0;
        int right = arr.length - 1;
        int cur = 0;
        
        while (left <= right) {
            cur = (left + right) >>> 1;
            if (arr[cur] > s) {                
                right = cur - 1;
            } else if (arr[cur] < s) {
                left = cur + 1;
            } else {
                return cur;
            }
        }
        
        return -1;
    }

    /**
     * 找到第一个s的下标，如果没有返回-1
     * @param arr
     * @param s
     * @return
     */
    public int search(int[] arr, int s) {
        int leftM = 0;
          
        int left = 0;
        int right = arr.length - 1;
        int cur = 0;
        
        while (left <= right) {
            cur = (left + right) >>> 1;
            if (arr[cur] > s) {                
                right = cur - 1;
            } else if (arr[cur] < s) {
                left = cur + 1;
                leftM = left;
            } else {
                if (arr[leftM] == arr[cur]) {//这个地方容易被忽略
                    return leftM;
                } else if (leftM < cur && arr[leftM] < arr[cur] && left < right) {
                    right = cur;
                } else {
                    return cur;
                }
            }
        }
        
        return -1;
    }
    
    @Test
    public void test() {
        int len = 10 + random.nextInt(100);
        int[] arr = new int[len];
        for (int i=0; i<len; i++) {
            arr[i] = random.nextInt(len);
        }
        Arrays.sort(arr);
        
        int s = arr[random.nextInt(len)];
        int i = search(arr, s);
        int j = 0;
        for (; j<len; j++) {
            if (arr[j] == s) {
                break;
            }
        }
        System.out.println(Arrays.toString(arr));
        System.out.println(i + " : " + arr[i] + " : " + s + " : " + j);
        Assert.assertEquals(j, i);
        int bs = bsearch(arr, s);
        Assert.assertEquals(s, arr[bs]);
        
        s = len;
        i = search(arr, s);
        bs = bsearch(arr, s);
        Assert.assertEquals(-1, i);
        Assert.assertEquals(-1, bs);
    }
    
    public static void main(String[] args) {
        BinSearch1st b = new BinSearch1st();
        for (int i=0; i<100; i++)
            b.test();
    }
}