二分查找

1. 算法实现流程

---

2. 实现代码

public class er_fen_cha_zhao {  
  public static void main(String[] args) {
        int[] array = {1,2,3,4,5,6,7,8,9,10};
        int target = 100;
        System.out.println("二分查找");
        int idx = binarySearch(array,target);
        if (idx != -1){
            System.out.println("目标存在，位置为array[" + idx +"] ==> " + array[idx]);
        }else System.out.println("目标不存在");
    }

    public static int binarySearch(int[] a, int t){
        int left = 0;
        int right = a.length - 1;
        int middle;
        while (left <= right){
            /**
             * 二分查找 求中点 用加号
             */
            middle = (right + left) / 2;
            /**
             * 当 left 和 right 很大的时候 相加再除以2就会产生整型溢出
             * 变换成
             * (right + left) / 2 ==> 
             * left/2 + right/2 ==> 
             * left + (-left/2 + right/2 ) ==> 
             * left + (right - left)/2
             */
            middle = left + (right - left)/2;
            /**
             * 方法二 右移运算 效率更高
             * (left + right) >>> 1
             */
            middle = (left + right) >>> 1;
            System.out.println("middle=>" + middle);
            if (a[middle] > t) right = middle - 1;
            if (a[middle] < t) left = middle + 1;
            if (a[middle] == t) return middle;
        }
        return -1;
    }
}

---

3. 面试题举例