算法查找——二分查找

简介: 算法查找——二分查找

🟡前言


21天挑战赛第二周,本文主要是讲述有关二分查找的知识


活动地址CSDN21天学习挑战赛


🟡概述


二分查找适用于有序数组中


e57a64d319d6427a8e0f1dc71df96bab.png


如下图所示,当我们要找到元素79时,先找数组的当中的元素81,由于79比81小,所以在左侧找(红框),重新定max和mid再寻找


5e812d41c21d42c58c93a3a3b178118e.png


🟡解题思路


  1. 先查找数组中最中间的元素(下标值向下取整)
  2. 如果要查找的元素值比中间的元素大,就将最大值改为中间值减一
    max = mid - 1
  3. 如果要查找的元素值比中间的元素小,就将最小值改为中间值加一
    min = mid + 1
  4. 重复上述步骤,直至找到所要查找的元素


🟡代码实现


public class BinarySearch {
    public static void main(String[] args) {
        // input data
        int[] a = {7,23,79,81,103,127,131,147};
        int key = 11;
        // 调用算法,并输出结果
        int result = search(a, key);
        System.out.println(result);
    }
    private static int search(int[] a,int key){
        // 初始化变量
        int min = 0;
        int max = a.length - 1;
        //通过循环找到要查找的元素
        while (true){
          int mid = (max + min) / 2 ;
          if(min > max){
        return -1;
      }
            // 情况1:比key大
            }else if(a[mid] > key){
                max = mid - 1;
            // 情况2:比key小     
            }else if(a[mid] < key){
                min = mid + 1;
            }
            //情况3:找到了
      else{
        return mid;
      }
        } 
    }
}


🟡结语


二分查找较简单,但是要注意数组一定要是有序的

相关文章
|
3月前
|
算法
【算法】二分查找——在排序数组中查找元素的第一个和最后一个位置
【算法】二分查找——在排序数组中查找元素的第一个和最后一个位置
|
12天前
|
算法 C# 索引
C#二分查找算法
C#二分查找算法
|
14天前
|
存储 算法 C语言
【C语言】二分查找算法
【C语言】二分查找算法
|
15天前
|
消息中间件 存储 算法
一文搞懂二分查找算法!
一文搞懂二分查找算法!
|
15天前
|
算法 Java 索引
数据结构与算法学习十五:常用查找算法介绍,线性排序、二分查找(折半查找)算法、差值查找算法、斐波那契(黄金分割法)查找算法
四种常用的查找算法:顺序查找、二分查找(折半查找)、插值查找和斐波那契查找,并提供了Java语言的实现代码和测试结果。
14 0
|
3月前
|
存储 算法 Java
深入算法基础二分查找数组
文章深入学习了二分查找算法的基础,通过实战例子详细解释了算法的逻辑流程,强调了确定合法搜索边界的重要性,并提供了Java语言的代码实现。
深入算法基础二分查找数组
|
3月前
|
算法
【算法】二分查找——二分查找
【算法】二分查找——二分查找
|
4月前
|
算法
【算法】二分查找(整数二分和浮点数二分)
算法学习——二分查找(整数二分和浮点数二分)
40 0
【算法】二分查找(整数二分和浮点数二分)
|
5月前
|
存储 算法 C语言
二分查找算法的概念、原理、效率以及使用C语言循环和数组的简单实现
二分查找算法的概念、原理、效率以及使用C语言循环和数组的简单实现
|
5月前
|
机器学习/深度学习 算法 索引
数据结构算法--1 顺序查找二分查找
**顺序查找时间复杂度为O(n)**,适合无序列表,可以通过`enumerate`或直接遍历索引来实现。**二分查找时间复杂度为O(logn)**,适用于有序列表,利用Python中`left`、`right`指针和`mid`点不断缩小搜索范围。效率上二分查找更优。