专栏首页后端Coder第四篇排序算法|二分查找

第四篇排序算法|二分查找

0x01,前言闲叙

现在回过头来想想学生时代的课程,可谓是用贬义词来形容,是自己的问题还是教学本身存在的问题,还是留给自己去思考和消化吧,因为每个人的故事都很不同。

0x02,本篇内容大概内容概览

0x03,什么是二分查找?

【百度百科介绍】二分查找也称为折半查找(Binary Search),它是一种效率较高的查找方法。但是,折半查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排序。

0x04,二分查找的特点

快速,不过要基于顺序存储,数据元素有序(从小到大/从大到小)的特点

0x05,二分查找代码实现

public class BinarySearchTest2 {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 16, 18, 20};
        int key = 12;
        int search = binarySearch(arr, key);
        System.out.println("search = " + search);
    }

    /**
     * @param arr 待查找数组元素
     * @param key 待查找元素
     * @return 元素在数组中的下标(index),找不到返回-1
     */
    public static int binarySearch(int[] arr, int key) {
        if (arr == null) {
            return -1;
        }
        int low = 0;
        int high = arr.length - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (key == arr[mid]) {
                return mid;
            } else if (key > arr[mid]) {
                low = mid + 1;
            } else if (key < arr[mid]) {
                high = mid - 1;
            }
        }
        return -1;
    }
}

0x06,二分查找程序图片版

0x07,二分查找的时间复杂度?

lg(n),注:以2为底

0x08,总结一下

对于二分查找而言,其难度也是在中等难度层级,好好理解一下吧,因为它本身包含这着你需要的东西

本文分享自微信公众号 - WwpwW(gh_245290c1861a),作者:后端Coder

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-10-19

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode111|独一无二的出现次数

    键值对HashMap的重要性真的是不言而喻的,因为它应用的太广泛了,可以说基本上你做应用就是使用它,和ArrayList的次数相差不大,所以你现在如果不懂的话,...

    码农王同学
  • 第三篇排序算法|选择排序

    其实对于这样的内容,自己没有一个很明确的讲解流程,一般还是按照下面的内容来说吧,先暂时看下大概的内容。

    码农王同学
  • LeetCode156|判断能否形成等差数列

    如果一个数列中,任意相邻两项的差总等于同一个常数,那么这个数列就称为 等差数列 。

    码农王同学
  • 聊聊「插入排序」的正确姿势

    面试官最爱考察的是一个被试者对知识掌握的灵活程度和熟练程度,当一道题目可以同时考察到被试者多个知识点的掌握程度和思考能力时,面试官最爱这样的题目,而且对于插入排...

    五分钟学算法
  • 【C语言笔记】关于数组的一个陷阱!

    所以,&a[2] - &a[0]的结果是8?但是,事实不是这样的!!让我们把其结果打印出来:

    正念君
  • LeetCode 40.最小的k个数

    输入整数数组 arr ,找出其中最小的 k 个数。例如,输入 4、5、1、6、2、7、3、8 这 8 个数字,则最小的 4 个数字是 1、2、3、4

    村雨遥
  • 算法:静态查找表(Static Search Table)(顺序查找、二分查找、插值查找、斐波纳契查找)

    查找表(Search table)是由同一类型的数据元素(或记录)构成的集合。关键字(key)是数据元素中某个数据项的值,又称为键值,用它可以表示一个数据元素,...

    s1mba
  • [数据结构与算法] 查找算法

    类似的,每一子段也可以用相同的方式分割 但顺序表长度n不一定刚好等于F[k]-1,所以需要将原来的顺序表长度n增加至F[k]-1。这里的k值只要能使得F[k]...

    时间静止不是简史
  • 第三阶段-Java常见对象:【第五章 Arrays类】

    BWH_Steven
  • [PHP] 看博客学习插入排序

    陶士涵

扫码关注云+社区

领取腾讯云代金券