二分查找_实现思路、步骤演示、常见问题

前提：有序的int数组

实现思路：

1. 判断数组是否为空，为空返回-1
2. 定义左边界 0
3. 定义右边界 数组长度-1
4. 定义中间索引m m=0
5. 创建循环 while(左<= 右）
6. 给M重新赋值 m=(左+右）>>> 1
7. 进行判断
   如果arr[m]=要找的数
   直接返回m
   如果arr[m] > 要找的数
   就把右边界变成M+1
   如果arr[m] < 要找的数
   就把左边界变成M-1
8. 异常返回-1

步骤演示：

public class Demo2 {

    public static void main(String[] args) {
        int[] arr=new int[]{1,2,3,4,5,6,7,8,9};
        int c=2;
        int i = test(arr, c);
        System.out.println(i);
    }

    public static int test(int[] arr,int c){
        if(arr==null){
            return -1;
        }
        //定义左边界
        int left =0;
        //右边界
        int right= arr.length-1;
        //中间索引
        while (left<=right){
            int m =left+right >>> 1;

            if (arr[m]==c){
                return m;
            } else //如果M的值比要比对的值小
                if (arr[m]<c) {
                    //把左边界改成m-1
                    left=m-1;
                } else //如果M的值比要比对的值大
                    if (arr[m]>c) {
                        right=m+1;
                    }
        }


        return -1;
    }
}

常见问题：

整数溢出问题：如果数组较长，两者相加只和超过int最大长度，则出现整数溢出
解决方法：使用>>>1
含义：除以2

附加：
面试中遇见二分查找选择题如何快速作答：

例子1：有一个有序表为1,5,8,11,19,22,31,35,40,45,48,49,50当二分查找值为48的结点时，查找成功需要比较的次数

技巧：奇数二分取中间，偶数二分取中间靠左，结果+1

逻辑演示：
第一次：该数值长度为13，是奇数，奇数二分取中间，也就是第七个（31这个数字）为中间索引m
第二次：剩下6个（31不算），中间索引为45
第三次：剩下3个，中间索引为二分取靠左，就是49
第四次：直接找到
答案：4次

代码验证：

public class Demo2 {

    public static void main(String[] args) {
        int[] arr=new int[]{1,5,8,11,19,22,31,35,40,45,48,49,50};
        int c=48;
//        test(arr, c);
        int i = test(arr, c);
        System.out.println(i);
    }

    public static int test(int[] arr,int c){
        if(arr==null){
            return -1;
        }
        int count=0;
        //定义左边界
        int left =0;
        //右边界
        int right= arr.length-1;
        //中间索引
        while (left<=right){
            int m =left+right >>> 1;

            if (arr[m]==c){
                count++;
                return count;
            } else //如果M的值比要比对的值小
                if (arr[m]<c) {
                    //把左边界改成m-1
                    left=m-1;
                    count++;
                } else //如果M的值比要比对的值大
                    if (arr[m]>c) {
                        right=m+1;
                        count++;
                    }
        }

        System.out.println(count);
        return -1;
    }
}	

例子2：在拥有128个元素的数组中二二分查找一个数, 需要比较的次数最多不超过多少次