二分查找

二分查找是一种查询效率非常高的查找算法。又称折半查找。

起初在数据结构中学习递归时实现二分查找，实际上不用递归也可以实现，毕竟递归是需要开辟额外的空间的来辅助查询。本文就介绍两种方法

优缺点
优点是比较次数少，查找速度快，平均性能好；

其缺点是要求待查表为有序表，且插入删除困难。

因此，折半查找方法适用于不经常变动而查找频繁的有序列表。
使用条件：查找序列是顺序结构，有序。

递归实现

//二分查找递归实现
    public static int binaryserach_recursion(int arr[],int aimnum,int low,int high){
        if (aimnum<arr[low] || aimnum > arr[high] || low > high){
            return -1;
        }
        int middle=(high+low)/2;
        if (aimnum > arr[middle]){
            return binaryserach_recursion(arr,aimnum,middle+1,high);
        }else if (aimnum < arr[middle]){
            return binaryserach_recursion(arr,aimnum,low,middle-1);
        }else {
            return middle;
        }
    }

非递归实现

为何有了递归我们还要去看非递归呢？因为我们知道每当我们调用一个函数JVM会在会在虚拟机栈中创建一个栈帧，那么当我们递归次数不多当然看不出来，当递归的次数过多，那么我们就会撑爆虚拟机栈导致栈溢出。

//二分查找非递归实现
    public static int binarySearch_loop(int arr[],int aimnum,int low,int high){
        if (aimnum<arr[low] || aimnum > arr[high] || low > high){
            return -1;
        }
        int middle=0;
        while (low <= high){
            middle=(low+high)/2;
            if (arr[middle] < aimnum){
                low = middle+1;
            }else if (arr[middle] > aimnum){
                high=middle-1;
            }
            else return middle;
        }
        return -1;
    }

注意点：

while (low <= high)：我们用的小于等于，而不是小于，这是保证一种情况可能少比一次，大家可以仔细思考。
int middle=(high+low)/2;：这里会有可能middle是int类型可能发生溢出的风险，这个我们在下面细讲。

附加问题：安全防溢出的两整数平均值算法

我们在前面看到我们每次算两个数的平均数数时使用的是int middle=(low+high)/2; 这个在我们int范围内当然没事，但是当我们数据过大会导致溢出问题！

特别对于二分查找我们可以这样修改

int right=(high-low+1)/2+low
如果对于平均，有一种专门的防溢出算法

public static int mean(int a, int b){
```
return (x & y) + ((x ^ y) >> 1);
```
}

相关一些题目

题一：无目标值，返回插入序号

题目描述：给定一个排序好的数组和目标值。如果在数组中找到目标值，则返回目标值索引号。如果在数组中找不到目标值，则返回可以插入的索引下标。
这个题目主要是我们最后肯定会返回一个索引，就是最后查到的索引，但是这个索引是目标值索引还是可插入索引不知道，这个时候我们可以将它抽象成一个类，两个属性：一个是索引值，一个是布尔值（是否是目标值）

class IndexNode{
```
int index;
Boolean flag;
public IndexNode(int index, Boolean flag) {
    this.index = index;
    this.flag = flag;
}
```
}
public class BinarySerach_withNode {

    public static IndexNode binarySerach(int arr[],int aimnum){
        IndexNode pos=new IndexNode(-1,false);
        int low=0;
        int high=arr.length-1;
        int middle=0;
        while (low <= high){
            middle=(high-low+1)/2+low;
            if (aimnum > arr[middle]){
                low=middle+1;
            }else if (aimnum < arr[middle]){
                high=middle-1;
            }else {
                pos.index=middle;
                if (arr[middle]==aimnum){
                    pos.flag=true;
                }else {
                    pos.flag=false;
                }
                break;
            }
        }
        return pos;
    }
    public static void main(String[] args) {
        int arr[]={
    1,2,3,4,5,67,75,88,99};
        IndexNode pos=binarySerach(arr,0);
        System.out.println(pos.index );
        System.out.println(pos.flag);
    }
}