二分查找算法的两种实现方式

作者: 阿犇专用 | 来源:发表于2017-09-15 09:57 被阅读0次

一、二分查找法(二分折半查找)

1、普通方法

/**
*@paramarr待查询数组
*@paramfindValue待查询值
*@return查询值索引
*/

private static int binaryFind(int arr[], int findValue) {
       //最小索引
       int lowerBound = 0;
       //最大索引
       int upperBound = arr.length - 1;
       //中间索引
       int middleIndex;
       //思想:1、当最小索引小于等于最大索引时
       //      2、获得middleIndex(中间索引),以此判断middleIndex对应的值和findValue(查找值)是否对等
       //      3、如果对等,则返回当前索引,否则改变最小和最大索引
       //      4、不对等的情况,如果当前middleIndex对应的值小于findValue,则改变最小索引为middleIndex+1,否则改变最大索引为middleIndex-1
       //      5、以此循环,最终得到findValue的索引
       while (lowerBound <= upperBound) {
           middleIndex = (lowerBound + upperBound) / 2;
           if (arr[middleIndex] == findValue) {
               return middleIndex;
           } else {
               if (arr[middleIndex] < findValue) {
                   lowerBound = middleIndex + 1;
               } else {
                   upperBound = middleIndex - 1;
               }
           }
       }
       return -1;
   }  

2、递归方法

 /**
 * 二分查找递归算法
 * @param arr 待查询数组
 * @param currentValue 待查询值
 * @param beginIndex 起始索引
 * @param endIndex 结束索引
 * @return 查询值索引
 */
private static int recursionBinaryFind(int[] arr, int currentValue, int beginIndex, int endIndex) {
    if (beginIndex <= endIndex) {
        int middleIndex = (beginIndex + endIndex) / 2;
        //当查找值等于中间值时
        if (currentValue == arr[middleIndex]) {
            return middleIndex;
            //当查找值大于中间值时,改变起始索引和结束索引,开始递归
        } else if (arr[middleIndex] < currentValue) {
            return recursionBinaryFind(arr, currentValue, middleIndex + 1, endIndex);
            //当查找值小于中间值时,改变起始索引和结束索引,开始递归
        } else{
            return recursionBinaryFind(arr, currentValue, beginIndex, middleIndex - 1);
        }
    } else {
        return -1;
    }
}

相关文章

网友评论

    本文标题:二分查找算法的两种实现方式

    本文链接:https://www.haomeiwen.com/subject/ixqssxtx.html