算法导论之二分查找

系统管理员 2022-03-21 12:08 280阅读 0赞

二分查找的前提是要进行查找的序列必须是有序的，这里我们以升序为例。

<table style="width:500px;"> 
 <tbody> 
  <tr> 
   <td>1</td> 
   <td>2</td> 
   <td>3</td> 
   <td>4</td> 
   <td>5</td> 
   <td>6</td> 
   <td>7</td> 
   <td>8</td> 
   <td>9</td> 
  </tr> 
 </tbody> 
</table>

start = 0, end = 8, mid = (0 + 8) / 2;

比如我们查找val = 2;

首先我们比较A\[mid\]和val, 如果val大，那么我们递归右边，否则我们递归左边。

#include <iostream>
    using namespace std;
    
    int A[] = {1,2,3,4,5,6,7,9};
    int len = sizeof(A)/sizeof(A[0]);
    
    int Binary(int start, int end, int val)
    {
        for (int j = start; j <= end; ++j) {
            if (A[j] == val)
                return j;
        }
        return -1;
    }
    
    int BinarySearch(int start, int end, int val)
    {
        if (start == 0 && end == 0 && A[0] == val)//只有一位元素
            return 0;
        if (start < end) {
            int mid = (start + end) / 2;
            if (A[mid] > val) {//递归左边
                BinarySearch(start, mid, val);
                return Binary(start, mid, val);
            }
            else {//递归右边
                BinarySearch(mid + 1, end, val);
                return Binary(mid + 1, end, val);
            }
        }
        return -1;
    }
    
    int main()
    {
        cout << BinarySearch(0, len - 1, 10) << endl;
        return 0;
    }

发表评论取消回复

表情：

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

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

相关阅读

相关简单算法之二分查找

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

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

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

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

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

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

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

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

相关《算法导论》读书笔记之第12章二叉查找树

/images/20220824/0ff7e3c1c69642548a45c7347bb5a286.png 摘要：　　本章介绍了二叉查找树的概念及操作。主要内容包括

刺骨的言语ヽ痛彻心扉/ 2022年08月26日 12:26/ 0 赞/ 200 阅读

相关 java之二分查找

二分查找的前提条件是数组中的元素必须已经排序，不管是按照升序还是降序排列。示例代码如下： //二分查找 import java.util.; p

本是古典何须时尚/ 2022年07月28日 00:26/ 0 赞/ 165 阅读

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

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

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

相关算法之二分查找

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

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

相关算法导论之二分查找

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

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

相关 Python之二分查找

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

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

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

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

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