使用二分法查找有序数组中指定的元素

使用二分法查找有序数组中指定的元素，二分法，就是折半查找，先从中间开始查询，如果中间的数小于查询的数，那么查询的区域就缩小到中间数以后的元素，如果中间数大于查询的数，那么查询的范围就缩小到下标为0到中间数，一直查询查询，直到找到要查询的数为止。对于折半查找，我这里有两种方法，代码如下：

第一种：

public static int getIndex(int[] arr,int target){
    //第一个元素的下标值
    int first = 0;
    //第二个元素的下标值
    int last = arr.length-1;
    //查找数的下标值
    int index=-1;
    while(first<=last){
        //中间下标值
        int middle = (first+last)/2;
        //等于
        if(arr[middle]==target){
            index = middle;
            break;
        }else if(arr[middle]>target){
            last=middle;
        }else if(arr[middle]<target){
            first=middle+1;
        }
    }
    return index;
}

这种方法是利用了while循环做的，对于简单的有序数组，它可以很快的查询出来，但是对于复杂的有序数组，查询结果就是错的，什么样的是复杂的有序数组呢？就是在一个有序数组中，有一个元素重复很多次，在这样的情况下，这段代码执行的结果是不正常的。

第二种：

/*使用递归实现二分法查找
* first  数组中第一个数的下标
* last  数组中最后一个数的下标
* target 查询的数
* arr 数组
* */
public  static  int  getIndex(int[] arr,int target,int first,int last){
    //如果数组中只有一个元素
    if(first==last){
        if(arr[first]==target){
            return first;
        }else {
            return -1;
        }
    }else{//数组中有很多的元素
        int avg = (first+last)/2;
        /*在二分查找中有：
        * 1.查询的数大于中间数
        * 2.查询的数小于中间数
        * 3查询的数等于中间数
        * */
        if(target==arr[avg]){
            //判断数组前面是否有一样的元素
            if(getIndex(arr,target,first,avg)==-1){//true 说明前面没有一样的值
                   return  avg;
            }else {
                return getIndex(arr,target,first,avg);
            }

        }else if(target>arr[avg]){
            return getIndex(arr,target,avg+1,last);
        }else if(target<arr[avg]){
            return getIndex(arr,target,first,avg);
        }
        return -1;
    }
}

使用递归实现二分法的查找，这段代码的执行能力就远远超过，第一种代码的执行能力，如果数组简单可以采用第一种方法，第一种方法相对于第二种方法比较容易理解，如果数组比较复杂，采用第二种方法。

今天就到这吧，如果还有其他方法，我们可以一起学习的！

以上者两种方法，也是我通过网络了解的，然后加了一些自己的见解，如有冒犯，请原谅！