Rubin's Blog

  • 首页
  • 关于作者
  • 隐私政策
享受恬静与美好~~~
分享生活的点点滴滴~~~
  1. 首页
  2. 数据结构和算法
  3. 正文

算法之二分查找

2022年 1月 4日 780点热度 0人点赞 0条评论

概念

二分查找(Binary Search)算法,也叫折半查找算法

当我们要从一个序列中查找一个元素的时候,二分查找是一种非常快速的查找算法

二分查找是针对有序数据集合的查找算法,如果是无序数据集合就遍历查找

本质

二分查找之所以快速,是因为它在匹配不成功的时候,每次都能排除剩余元素中一半的元素。因此可能包含目标元素的有效范围就收缩得很快,而不像顺序查找那样,每次仅能排除一个元素。

小例子

一个有序的数组中查找某个数字是否存在:

package com.rubin.algorithm.search;

public class BinarySearch {

    /**
     * 经典二分查找
     *
     * @param nums
     * @param item
     * @return
     */
    public static int normalBinarySearch(int[] nums, int item) {
        int low = 0, high = nums.length - 1, mid;
        while (low <= high) {
            mid = (low + high) / 2;
            int midValue = nums[mid];
            if (midValue == item) {
                return mid;
            } else if (midValue > item) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return -1;
    }

    /**
     * 递归二分查找
     *
     * @param nums
     * @param item
     * @return
     */
    public static int recursionBinarySearch(int[] nums, int item) {
        return doRecursionBinarySearch(nums, item, 0, nums.length - 1);
    }

    private static int doRecursionBinarySearch(int[] nums, int item, int low, int high) {
        if (low > high) {
            return -1;
        }
        int mid = (low + high) / 2;
        int midValue = nums[mid];
        if (midValue == item) {
            return mid;
        } else if (midValue > item) {
            return doRecursionBinarySearch(nums, item, low, mid - 1);
        } else {
            return doRecursionBinarySearch(nums, item, mid + 1, high);
        }
    }

    /**
     * 一个有序数组有一个数出现1次,其他数出现2次,找出出现一次的数
     *
     * @param nums
     * @return
     */
    public static int onceBinarySearch(int[] nums) {
        int low = 0, high = nums.length - 1, mid;
        while (low < high) {
            mid = (low + high) / 2;
            // 偶数位
            if (mid % 2 == 0) {
                // 偶数位跟后面的相等 说明前面的都对
                if (nums[mid] == nums[mid + 1]) {
                    low = mid + 1;
                }
                // 偶数位跟前面的相等 说明后面的都对
                else if (nums[mid] == nums[mid - 1]) {
                    high = mid - 1;
                }
                // 前后都不相等 就是该数
                else {
                    return nums[mid];
                }
            }
            // 奇数位
            else {
                // 奇数位跟后面的相等 说明后的都对
                if (nums[mid] == nums[mid + 1]) {
                    high = mid - 1;
                }
                // 奇数位跟前面的相等 说明前的都对
                else if (nums[mid] == nums[mid - 1]) {
                    low = mid + 1;
                }
                // 前后都不相等 就是该数
                else {
                    return nums[mid];
                }
            }
        }
        // low == high
        return nums[low];
    }

    public static void main(String[] args) {
        int[] nums = {2, 4, 5, 7, 10, 24, 36, 89};
        System.out.println(normalBinarySearch(nums, 5));
        System.out.println(recursionBinarySearch(nums, 2));
        int[] onceNums = {1, 1, 2, 2, 3, 4, 4, 5, 5};
        System.out.println(onceBinarySearch(onceNums));
    }

}

时间复杂度

时间复杂度就是 O(logn)

优缺点

优点:速度快,不占空间,不开辟新空间

缺点:必须是有序的数组,数据量太小没有意义,但数据量也不能太大,因为数组要占用连续的空间

应用

有序的查找都可以使用二分法。

以上就是本文的全部内容。欢迎小伙伴们积极留言交流~~~

本作品采用 知识共享署名 4.0 国际许可协议 进行许可
标签: 数据结构和算法
最后更新:2022年 6月 9日

RubinChu

一个快乐的小逗比~~~

打赏 点赞
< 上一篇
下一篇 >

文章评论

razz evil exclaim smile redface biggrin eek confused idea lol mad twisted rolleyes wink cool arrow neutral cry mrgreen drooling persevering
取消回复
文章目录
  • 概念
  • 本质
  • 小例子
  • 时间复杂度
  • 优缺点
  • 应用
最新 热点 随机
最新 热点 随机
问题记录之Chrome设置屏蔽Https禁止调用Http行为 问题记录之Mac设置软链接 问题记录之JDK8连接MySQL数据库失败 面试系列之自我介绍 面试总结 算法思维
JVM简介 问题记录之Mac设置软链接 Elasticsearch之入门使用 SpringCloud之分布式链路追踪 SpringBoot之内嵌Tomcat SpringMVC高级技术

COPYRIGHT © 2021 rubinchu.com. ALL RIGHTS RESERVED.

Theme Kratos Made By Seaton Jiang

京ICP备19039146号-1