首页 > 编程语言 > 详细

二分查找算法

时间:2020-04-24 22:41:02      阅读:59      评论:0      收藏:0      [点我收藏+]

二分查找

1. 算法介绍

二分查找只适用于从有序的数列中进行查找,将数列排序后再进行查找

二分查找算法的运行时间为 O(log2 n),即 100 个数,最多需要 7 次:(2 ^ 6 < 100 < 2 ^ 7)

2. 二分查找-递归

  • 首先确定数组中间的下标:mid = (left + right) / 2
  • 然后让需要查找的数 findVal 与 arr[mid] 进行比较
    • findVal > arr[mid],则递归向右查找
    • findVal < arr[mid],则递归向左查找
    • findVal == arr[mid],则找到,返回即可

当找到或者递归完整个数组后结束递归!

2.1 代码实现(递归)

package cn.imut;

import sun.security.provider.MD2;

public class BinarySearch {

    public static void main(String[] args) {
        int[] arr = {1, 3, 4, 7, 9, 11, 14, 15, 20, 1000};
        int resIndex = binarySearch(arr,0,arr.length - 1, 1000);
        System.out.println("要查询的数字的下标为:" + resIndex);
    }

    /**
     * 二分查找
     * @param arr 数组
     * @param left 左索引
     * @param right 右索引
     * @param findVal 要查找的数字
     * @return 返回其下标,没找到则返回 -1
     */
    public static int binarySearch(int[] arr, int left, int right, int findVal) {

        //当left > right 时,说明数组已经递归完毕,但是还没有找到!
        if(left > right) {
            return -1;
        }
        int mid = (left + right) / 2;
        int midVal = arr[mid];

        if(findVal > midVal) {
            return binarySearch(arr, mid + 1, right, findVal);
        }else if(findVal < midVal) {
            return binarySearch(arr, left, mid - 1, findVal);
        }else {
            return mid;
        }
    }

}

2.2 加强版

倘若有多个相同的数字要查询,eg:{1, 8, 10, 22, 1000, 1000, 1000, 22222},查询数字 1000

  • 找到mid索引时,不要立刻返回
  • 向 mid 索引的左边扫描,将满足 1000的下标全都加入集合
  • 向 mid 索引的右边扫描,将满足 1000的下标全都加入集合
  • 返回集合即可
public static ArrayList<Integer> binarySearch2(int[] arr, int left, int right, int findVal) {

    //当left > right 时,说明数组已经递归完毕,但是还没有找到!
    if(left > right) {
        return new ArrayList<Integer>();
    }
    int mid = (left + right) / 2;
    int midVal = arr[mid];

    if(findVal > midVal) {
        return binarySearch2(arr, mid + 1, right, findVal);
    }else if(findVal < midVal) {
        return binarySearch2(arr, left, mid - 1, findVal);
    }else {
        //此时不能直接返回,而是向两侧分别查询
        ArrayList<Integer> list = new ArrayList<>();
        int temp = mid - 1;
        while (temp >= 0 && arr[temp] == findVal) {
            //找到,放入集合
            list.add(temp);
            temp -= 1;
        }

        temp = mid + 1;
        while (temp <= arr.length - 1 && arr[temp] == findVal) {
            list.add(temp);
            temp += 1;
        }
        return list;
    }
}

3. 二分查找-非递归

package cn.imut;

public class BinarySearchNoRecur {

    public static void main(String[] args) {

        int[] arr = {1, 3, 6, 19, 22, 40};

        int index = binarySearch(arr,40);
        System.out.println(index);
    }

    /**
     * 二分查找非递归实现
     * @param arr 数组,升序排序
     * @param target 要查找的数
     * @return 返回对应下标, -1表示没有找到
     */
    public static int binarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if(arr[mid] == target) {
                return mid;
            }else if(arr[mid] > target) {
                right = mid - 1;        //向左继续查找
            }else {
                left = mid + 1;         //向右继续查找
            }
        }
        return -1;
    }
}

二分查找算法

原文:https://www.cnblogs.com/yfyyy/p/12770536.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!