一.二分查找

对于有序数组,目标是要在数组内查找目标值target。若查找成功则返回索引值，返回失败返回-1.

因此需确定两个指针i，j  。令。

查找失败的结果即是i>j或j<i,此时返回-1，提示无所查找数据。

而当i与j之间还有数据时，此时就需设置一个中间值，因此我们令(即令为i和j中间的数为中间值，此处为向下取整，在java中两个整数除法会自动取整，因此无需此floor函数)。因为这个一个有序数组，因此若m指向的数据的值>target，则令j=m-1。反之，则令i=m+1。以此循环。直至查找成功或者出现失败的情况

简单代码如下

public class Main {
    public static void main(String[] args) {
        int[] a={7,13,21,30,38,44,52,53};
        int target = 21;
        int position = binarySearchBasic(a,target);
        if(position == -1){
            System.out.println("查询不到该数据");
        }else{
            System.out.println("查询到数据位置为"+position);
        }
    }

    //二分查找
    public static int binarySearchBasic(int [] a,int target){
        int i = 0,j = a.length - 1;//设置指针
        while( i <= j){
            int m= ( i + j )/ 2;
            if(a[m]<target){
                i= m + 1;//目标在右
            } else if (a[m]>target) {
                j= m - 1;//目标在左
            }else{
                return m;//目标查找成功
            }
        }
        return -1;
    }

}

详细问题：

1.为什么while循环中使用i<=j,而非i<j。

        可以举一个简单的例子，有五个数据。此时target为1。

第一次循环，m=2。接下来i=0,j=1;

第二次循环，m=0。接下来i=1,j=1;

此时不满足循环情况，退出循环，导致查询失败。因此在这段代码中i<=j。

2.中间值m的算法有无问题。

在这个测试用例中是没有问题，但是假如这个数组很大很大。i=0.j=int的最大值。此时m很显然会存在超过int上限的情况，此时输出会为一个负数。原理是在java中二进制存在符号位，同一个数据的二进制表现形式一样，但是在java中由于超过int类型上限，因此将二进制数的第一位认定为了符号位导致了负数。

解决这个问题就需要用无符号的运算符。将所有二进制数依次向右移一位就可以看做是对原数据进行了一次除2的处理。就可以解决这个问题。即令 m = i + j >>> 1。还可以让代码在多种语言中都可以用。

3.代码的可阅读性

在我的代码中出现了>符号，但若是全为<符号可能会更方便阅读。

这是针对以上问题修改后的代码

public class Main {
    public static void main(String[] args) {
        int[] a={7,13,21,30,38,44,52,53};
        int target = 21;
        int position = binarySearchBasic(a,target);
        if(position == -1){
            System.out.println("查询不到该数据");
        }else{
            System.out.println("查询到数据位置为"+position);
        }
    }

    //二分查找
    public static int binarySearchBasic(int [] a,int target){
        int i = 0,j = a.length - 1;//设置指针
        while( i <= j){
            int m= ( i + j ) >>> 1;
            if(a[m] < target){
                i= m + 1;//目标在右
            } else if (target < a[m]) {
                j= m - 1;//目标在左
            }else{
                return m;//目标查找成功
            }
        }
        return -1;
    }

}

接下来对代码进行一些修改（请看注释）

也是可以实现的

public class Main {
    public static void main(String[] args) {
        int[] a={7,13,21,30,38,44,52,53};
        int target = 21;
        int position = binarySearchBasic(a,target);
        if(position == -1){
            System.out.println("查询不到该数据");
        }else{
            System.out.println("查询到数据位置为"+position);
        }
    }

    //二分查找
    public static int binarySearchBasic(int [] a,int target){
        int i = 0,j = a.length;//改动1
        while( i < j){         //改动2
            int m= ( i + j ) >>> 1;
            if(a[m] < target){
                i= m + 1 ;        
            } else if (target < a[m]) {
                j= m;           //改动3
            }else{
                return m;//目标查找成功
            }
        }
        return -1;
    }

}