首页 > 编程语言 >c++算法:二分

c++算法:二分

时间:2023-05-31 17:55:38浏览次数:43  
标签:二分 int 元素 c++ 算法 查找

算法中,有一种比线性查找算力费得更少的一种算法思想,叫“分治”,今天讲的是分治里的二分查找:

借助 (low+high)/2公式,找到搜索区域内的中间元素。图 1 中,搜索区域内中间元素的位置是 ⌊(1+10)/2⌋=5,因此中间元素是 27,此元素显然不是要找的目标元素。然后就是缩小范围。

 下面就是一个二分查找的c++程序:

 1 #include<iostream>
 2 #include<algorithm>
 3 using namespace std;
 4 int a[500005];
 5 int n;
 6 bool sreach(int key)
 7 {
 8     int mid,left=1,right=n;
 9     while(left<=right)//遍历a[]
10     {
11         mid=(left+right)/2;//寻找中间值
12         if(a[mid]==key)//判断是否查到
13         {
14             return true;
15         }
16         else if(a[mid]<key)
17         {
18             left=mid+1;//缩小范围
19         }
20         else
21         {
22             right=mid-1;//缩小范围
23         }
24     }
25     return false;
26 }
27 int main()
28 {
29     int t,m;
30     scanf("%d",&n);
31     for(int i=1;i<=n;i++)
32     {
33         scanf("%d",&a[i]);
34     }
35     sort(a+1,a+n+1);
36     scanf("%d",&t);
37     while(t--)
38     {
39         cin >> m;
40         if(sreach(m))
41         {
42             printf("YES");
43             cout << endl;
44         }
45         else
46         {
47             printf("NO");
48             cout << endl;
49         }
50     }
51     return 0;
52 } 

 关于二分到现在基本讲完了,大家拜拜~~

标签:二分,int,元素,c++,算法,查找
From: https://www.cnblogs.com/xuexue1234/p/cpluspluserfen_.html

相关文章

  • 限流算法
    固定窗口缺陷:最简单,但是不能精确限制,由于是计算的时间差,比如每10秒只能10个请求,8-10秒请求了10个,那么10-18秒就也无法请求了importjava.util.concurrent.atomic.AtomicInteger;importjava.util.concurrent.atomic.AtomicLong;publicclassMyFixedWindow{privatef......
  • C++ 初始化赋值
    把值写在小括号中,等于号可以省略(C++标准)inta=(15);intb(20);把值写在花括号中,等于号也可以省略(C++11标准),统一初始化列表注意:在Linux平台下,编译需要加-std=c++11参数inta={15};inta{15};......
  • NEFU 635(二分+枚举)
    题目:TwinkleTwinkleLittleStar 题意:就是给n个点的坐标,然后在这个图形中找出一个边长最小的正方形,要求正方形的边平行于坐标轴且覆盖的点大于等于k个。#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>usingnamespacestd;constintN=20......
  • 等比数列二分求和
    今天我们学习如何有效地求表达式的值。对于这个问题,用二分解决比较好。(1)当时,(2)当时,那么有    (3)当时,那么有   代码:#include<iostream>#include<string.h>#include<stdio.h>usingnamespacestd;constintM=1000000007;typedeflonglongLL;LLpower(LLa,LL......
  • 二分查找
    我们知道二分查找的基础写法有三种:左闭右闭区间publicstaticintbinsearch(int[]nums,inttarget){intl=0,r=nums.length-1;while(l<=r){intm=(l+r)/2;if(nums[m]==target)returnm;......
  • 欧几里得算法求最大公约数
    欧几里得算法又称辗转相除法,是指用于计算两个非负整数a,b的最大公约数。以除数和余数反复做除法运算,当余数为0时,取当前算式除数为最大公约数假如需要求18和30两个正整数的最大公约数:调用函数:print(gcd(18,30)),a,b值变化如下a    b30÷18=1……1218÷12=1……......
  • Snap算法学习01-02关于net节点、边、权值、标签的读写操作——netinf中cascades层级信
      Model可选值—— 0:exponential,  1:powerlaw,  2:rayleigh"                                      ......
  • Bellman-Ford算法——为什么要循环n-1次?图有n个点,又不能有回路,所以最短路径最多n-1边
    单源最短路径给定一个图,和一个源顶点src,找到从src到其它所有所有顶点的最短路径,图中可能含有负权值的边。Dijksra的算法是一个贪婪算法,时间复杂度是O(VLogV)(使用最小堆)。但是迪杰斯特拉算法在有负权值边的图中不适用,Bellman-Ford适合这样的图。在网络路由中,该算法会被用作距......
  • 算法总结——堆栈、字符串、数组类题目
    先说stack的题目stack的实现:链表,数组题目:(1)简单的:minstack,一个数组实现三个stack(2)经典的stack问题:经典汉诺塔问题,逆波兰式计算或者产生逆波兰式,简化文件路径,验证括号对是否合法,找出最长有效括号(贪心+stack求解)(3)涉及tree的遍历问题:tree中序遍历的迭代解法,二叉搜索树的两节点和(twosu......
  • 石子合并(GarsiaWachs算法)
    对于石子合并问题,有一个最好的算法,那就是GarsiaWachs算法。时间复杂度为O(n^2)。它的步骤如下:设序列是stone[],从左往右,找一个满足stone[k-1]<= stone[k+1]的k,找到后合并stone[k]和stone[k-1],再从当前位置开始向左找最大的j,使其满足stone[j]> stone[k]+stone[k-1],插到j的后面就......