简单算法之二分查找

水深无声 2023-10-09 15:38 45阅读 0赞

## 二分查找 ##

##### 算法介绍 #####

二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。

##### 算法原理 #####

拿到数组起始下标（left）和结束下标（right）加起来除以二，就是这个数组的中间下标（mid），然后使用需要查找的这个数去与中间下标上的数字相比，比中间下标的数大，就把left 赋值为mid+1，反之就更改right 为 mid-1。重复此循环知道找到这个数为止。  
一次运算排除一半的数字，就不用for循环一个一个找，效率更高，但是使用折半查找必须要是有序的。

##### 代码块 #####

public class DichotomyQuery {
        
        public static void main(String[] args) {
        
            int[] arr = {
        1,2,3,4,5,6,7,8,9};
            int left = 0,rigth = arr.length-1;
            int mid = 0;
            int q = 6;
            while (left<rigth){
        
                mid = (rigth+left)/2;
                if(q>arr[mid]){
        
                    left = mid + 1;
                }
                if(q<arr[mid]){
        
                    rigth = mid -1;
                }
            }
            System.out.println(rigth);
        }
    }

##### 运行结果 #####

![在这里插入图片描述][076e93f0cbc54f9f8d7c252dd7716db2.png_pic_center]

[076e93f0cbc54f9f8d7c252dd7716db2.png_pic_center]: https://img-blog.csdnimg.cn/076e93f0cbc54f9f8d7c252dd7716db2.png#pic_center

发表评论取消回复

表情：

评论列表（有 0 条评论，45人围观）

还没有评论，来说两句吧...

相关阅读

相关【算法】数组查找之二分查找

二分查找要求：有序无重复元素题目 [704. 二分查找 - 力扣（LeetCode）][704. _ - _LeetCode]

心已赠人/ 2024年03月27日 12:41/ 0 赞/ 65 阅读

相关简单算法之二分查找

二分查找算法介绍二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键

水深无声/ 2023年10月09日 15:38/ 0 赞/ 46 阅读

相关 C语言经典查找算法之二分查找（详解）

文章目录一、查找算法二、二分查找算法一、查找算法查找是在大量的信息中寻找一个特定的信息元素，在计算机应用中，查找是常用的基本运算

墨蓝/ 2023年01月03日 14:19/ 0 赞/ 130 阅读

相关算法刻意练习之二分查找

1 三个前提条件 1. 目标函数单调性（单调递增或者递减）。二分的数据必须是有序的，这样可以通过它的某些特征排除掉比如说前半部分或后半部分； 2. 存在上下界（

古城微笑少年丶/ 2022年12月08日 14:21/ 0 赞/ 191 阅读

相关经典搜索算法之二分查找与二叉查找树

1.二分查找二分查找也称为折半查找，它是一种效率较高的查找方法。二分查找的使用前提是线性表已经按照大小排好了序。这种方法充分利用了元素间的次序关系，采用分治策略。基

女爷i/ 2022年05月16日 05:56/ 0 赞/ 190 阅读

相关算法之二分查找

概念二分查找针对的是一个有序的数据集合，查找思想有点类似分治思想，每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到想要查找的元素，或是区间被缩小

柔光的暖阳◎/ 2022年04月17日 03:58/ 0 赞/ 200 阅读

相关算法导论之二分查找

二分查找的前提是要进行查找的序列必须是有序的，这里我们以升序为例。 <table style="width:500px;"> <tbody> <tr> <t

系统管理员/ 2022年03月21日 12:08/ 0 赞/ 279 阅读

相关每周一算法之二分查找(Kotlin描述)

简述: 从这篇文章起就会开启另一个系列就是上篇文章中提到的每周学习一个基本算法，会结合LeetCode上题目来做分析。解题的语言一般是Kotlin或Java. 如果涉及到一些有

悠悠/ 2022年02月24日 15:18/ 0 赞/ 183 阅读

相关 Python之二分查找

二分查找：将查找范围平分为二，对比要查找的属于哪一部分，再将那部分范围继续平分为二，对比属于哪部分，以此类推，最终得到要查找的对象，即为二分查找。注意：查找对象必须

忘是亡心i/ 2022年02月20日 01:25/ 0 赞/ 236 阅读

相关死磕算法之二分查找法

二分查找又称折半算法，此算法作为一个经典的查找算法是我们不得不掌握的算法这个算法查找的前提是查找的数据是有序的，我们以数组为例，使用二分查找法进行查找的时候我们应该先...

红太狼/ 2021年04月19日 14:20/ 0 赞/ 464 阅读