-
个人简介
二分查找
#include <bits/stdc++.h> using namespace std; //如果存在x 这个函数返回1 否则返回0 int bs(int x){//查找数字x 在a数组当中有没有出现过 int l=1,r=n; while(l<=r){ int m=(l+r)/2;//mid if(a[m]==x) return 1; if(a[m]>x) r=m-1; if(a[m]<x) l=m+1; } return 0; } //查找数字x第一次出现的位置 int bs2(int x){//查找数字x 在a数组当中有没有出现过 int l=1,r=n,ans=-1;//细节1:左右指针的初始值 while(l<=r){//细节2:while循环里面的条件一定是 l<=r int m=(l+r)/2;//mid if(a[m]==x) ans=m,r=m-1; if(a[m]>x) r=m-1;//细节3:仔细思考指针是怎么样移动的 if(a[m]<x) l=m+1; } return ans; } //查找数字x最后一次出现的位置 int bs3(int x){//查找数字x 在a数组当中有没有出现过 int l=1,r=n,ans=-1;//细节1:左右指针的初始值 while(l<=r){//细节2:while循环里面的条件一定是 l<=r int m=(l+r)/2;//mid if(a[m]==x) ans=m,l=m+1; if(a[m]>x) r=m-1;//细节3:仔细思考指针是怎么样移动的 if(a[m]<x) l=m+1; } return ans; } //我们结合bs2和bs3 可以帮助我们快速的查找某个数字在 数组里面一共出现了多少次 6---> 1 2 3 4 5 6 //查找大于x 第一次出现的位置 int bs4(int x){ int l=1,r=n,ans=-1; while(l<=r){ int m=(l+r)/2; if(a[m]>x) ans=m,r=m-1; else l=m+1; } return ans; } //查找大于等于x 第一次出现的位置 int bs5(int x){ int l=1,r=n,ans=-1; while(l<=r){ int m=(l+r)/2; if(a[m]>=x) ans=m,r=m-1; else l=m+1; } return ans; } //查找小于x 最后一次出现的位置 int bs6(int x){ int l=1,r=n,ans=-1; while(l<=r){ int m=(l+r)/2; if(a[m]<x) ans=m,l=m+1; else r=m-1; } return ans; } //查找小于等于x 最后一次出现的位置 int bs7(int x){ int l=1,r=n,ans=-1; while(l<=r){ int m=(l+r)/2; if(a[m]<=x) ans=m,l=m+1; else r=m-1; } return ans; } //结合bs5和bs7 可以快速的计算在数组中 L到R这段范围内的数字有多少个 int main() { return 0; } -
通过的题目
- P1000
- P1001
- P1002
- P1003
- P1004
- P1005
- P1007
- P1008
- P1009
- P1010
- P1013
- P1014
- P1015
- P1016
- P1017
- P1019
- P1021
- P1022
- P1025
- P1026
- P1027
- P1028
- P1029
- P1030
- P1031
- P1032
- P1033
- P1034
- P1035
- P1036
- P1037
- P1039
- P1040
- P1042
- P1043
- P1044
- P1045
- P1046
- P1047
- P1049
- P1050
- P1051
- P1052
- P1053
- P1054
- P1055
- P1056
- P1065
- P1066
- P1067
- P1068
- P1069
- P1072
- P1073
- P1074
- P1076
- P1077
- P1082
- P1085
- P1086
- P1087
- P1088
- P1089
- P1091
- P1097
- P1099
- P1105
- P1107
- P1109
- P1110
- P1119
- P1122
- P1129
- P1145
- P1149
- P1152
- P1156
- P1157
- P1158
- P1160
- P1161
- P1162
- P1164
- P1165
- P1166
- P1168
- P1169
- P1172
- P1174
- P1175
- P1180
- P1181
- P1182
- P1183
- P1184
- P1204
- P1205
- P1206
- P1212
- P1213
- P1219
- P1225
- P1229
- P1231
- P1232
- P1237
- P2542
- P1243
- P1245
- P1247
- P1248
- P1249
- P1255
- P1258
- P1260
- P1261
- P1263
- P1264
- P1269
- P1294
- P1295
- P1296
- P1297
- P1299
- P1300
- P1304
- P1306
- P1315
- P1317
- P1318
- P1319
- P1320
- P1324
- P1325
- P1326
- P1328
- P1335
- P1337
- P1340
- P1343
- P1358
- P1367
- P1384
- P1385
- P1386
- P1388
- P1390
- P1391
- P1393
- P1397
- P1398
- P1404
- P2590
- P2591
- P2592
- P2608
- P2609
- P2615
- P2619
- P2620
- P2621
- P2623
- P2624
- P2625
- P2627
- P2628
- P2630
- P2631
- P2632
- P2637
- P1410
- P1411
- P1412
- P1413
- P1414
- P1415
- P1417
- P1420
- P1440
- P1443
- P1451
- P1455
- P1456
- P1458
- P1459
- P1465
- P1486
- P1489
- P1491
- P1493
- P1505
- P1507
- P1509
- P1510
- P1515
- P1532
- P1547
- P1548
- P1551
- P1553
- P1558
- P1589
- P1591
- P1592
- P1594
- P1595
- P1597
- P1599
- P1600
- P1602
- P1603
- P1604
- P1605
- P1606
- P1609
- P1613
- P1614
- P1620
- P1625
- P1628
- P1631
- P1632
- P1633
- P1634
- P1636
- P1637
- P1639
- P1646
- P1650
- P1666
- P1667
- P1669
- P1687
- P1688
- P1689
- P1691
- P1695
- P1696
- P1699
- P1704
- P1707
- P1710
- P1711
- P1716
- P1720
- P1721
- P1726
- P1731
- P1738
- P1740
- P1756
- P1758
- P1759
- P1779
- P1783
- P1793
- P1808
- P1815
- P1819
- P1826
- P1829
- P1830
- P1831
- P1832
- P1834
- P1835
- P1905
- P1906
- P1907
- P1908
- P1909
- P1925
- P1927
- P1928
- P1931
- P1932
- P1947
- P1951
- P1959
- P1961
- P1973
- P1995
- P1997
- P2002
- P2016
- P2023
- P2033
- P2035
- P2040
- P2053
- P2054
- P2056
- P2061
- P2084
- P2107
- P2138
- P2161
- P2166
- P2173
- P2175
- P2180
- P2192
- P2194
- P2203
- P2211
- P2219
- P2237
- P2242
- P2244
- P2246
- P2248
- P2250
- P2256
- P2259
- P2260
- P2261
- P2262
- P2263
- P2264
- P2265
- P2266
- P2267
- P2268
- P2271
- P2273
- P2274
- P2277
- P3360
- P2280
- P2281
- P2282
- P2283
- P2286
- P2292
- P2298
- P2299
- P2301
- P2307
- P2317
- P2337
- P2338
- P2339
- P2340
- P2346
- P2354
- P2360
- P2384
- P2386
- P2391
- P2405
- P3238
- P2416
- P2533
- P2465
- P2527
- P2563
- P2504
- P2506
- P2508
- P2510
- P2518
- P2522
- P2525
- P2540
- P2534
- P2536
- P2551
- P2545
- P2549
- P2550
- P2646
- P2647
- P2648
- P2668
- P2669
- P2670
- P2693
- P2702
- P2705
- P2708
- P2725
- P2731
- P2745
- P2781
- P2784
- P2972
- P3237
- P3239
- P3242
- P3269
- P3277
- P3281
- P3284
- P3286
- P3287
- P3288
- P3290
- P3291
- P3293
- P3294
- P3295
- P3296
- P3297
- P3298
- P3309
- P3315
- P3318
- P3320
- P3325
- P3326
- P3327
- P3328
- P3332
- P3333
- P3334
- P3342
- P3368
- P3383
- P3371
- P3372
- P3378
- P3384
- P3393
- P3401
- P3407
- P3409
- P3416
- P3421
- P3422
- P3423
- P3436
- P3443
- P3453
- P3462
- P3479
- P3480
- P3483
- P3484
- P3489
- P3490
- P3499
- P3520
- P3522
- P3527
- P3619
- P3636
- P3645
- P3651
- P3653
- P3659
- P3811
- P3812
- P3837
- P3853
- P3896
- P3924
- P3925
- P3928
- P3929
- P3943
- P3944
- P3945
- P3947
- P3949
- P4030
- P4153
- P4156
- P4387
- P4542
- P4553
- P4602
- P4854
- P4879
- P4897
- P4929
- P4933
- P4941
- P4940
- P4956
- P4978
- P5594
- P5244
- P5042
- P5063
- P5107
- P5124
- P5131
- P5143
- P5144
- P5146
- P5147
- P5152
- P5153
- P5154
- P5180
- P5181
- P5182
- P5183
- P5184
- P5186
- P5209
- P5240
- P5241
- P5242
- P5243
- P5250
- P5251
- P5252
- P5288
- P5306
- P5307
- P5378
- P5379
- P5380
- P5386
- P5387
- P5388
- P5391
- P5393
- P5394
- P5400
- P5427
- P5428
- P5429
- P5442
- P5575
- 4335
- 4338
- 4339
- 4602
- 4656
- 4657
- 4814
- 4856
- 4956
- 5042
- 5061
- GESP121
- T1262
- GESP012305
- GESP012306
- GESP1135
- GESP202303C2T2
- 5410
- 5415
- 5416
- 5417
- 5421
- 5429
- 5430
- 5432
- 5436
- G1192
- 5457
- 5460
- 5461
- 5473
- 5474
- 5476
- 5477
- 5491
- 5505
- 5510
- 5511
- 5512
- 5513
- 5514
- 5517
- 5518
- T4
- T1
- T2
- 5544
- 5576
- 5595
- 5620
- 5621
- 5624
- 5626
- 5628
- 5629
- 5630
- 5631
- 5645
-
最近活动
- 南海区赛_最终模拟_COPY版本 作业
- 南海区赛_易错点测试题 OI
- 南海区赛_最终模拟 OI
- 区赛_综合复习 作业
- 王老师_区赛复习9 作业
- 王老师_C++区赛模拟2 OI
- 王老师_C++区赛模拟1 OI
- 王老师_区赛复习7 作业
- 南海区赛_小学组_历年_前两题 作业
- 王老师_区赛复习5 ACM/ICPC
- 周三晚_刷题班_1_COPY版本 作业
- 王老师_区赛冲刺2_COPY版本 作业
- for循环 总复习 作业
- 王老师_区赛复习4_COPY版本 作业
- 周五晚_练习2 作业
- 王老师_区赛复习 4 OI
- 王老师_区赛冲刺2 OI
- 王老师_区赛复习3_COPY版本 作业
- 王老师_区赛复习3 OI
- 王老师_区赛复习2_COPY版本 作业
- 王老师_区赛复习1_COPY版本 作业
- 王老师_区赛复习1 OI
- 王老师_班级小测 作业
- 王老师_字符串+进制转换复习 作业
- 王老师_尺取法1班级 作业
- 王老师_前缀和进阶班级 作业
- 王老师_区间贪心 作业
- 王老师_班级小练 作业
- 王老师_国庆班级1_第三次课_综合性测试+讲解 作业
- 王老师_国庆班级1_第二次课_二维前缀和+二维差分 作业
- 王老师_国庆班级1_第一次课_简单贪心 作业
- 王老师班级_阶段性小测 作业
- 王老师_结构体排序+递推 作业
- 王老师_结构体+函数+进制转换+连续性问题 作业
-
最近编写的题解
-
Stat
-
Rating
题目标签
- 循环
- 154
- 分支
- 63
- 一维数组
- 61
- 枚举
- 46
- 嵌套循环
- 45
- 累加
- 41
- 基础问题
- 37
- 字符串
- 36
- 统计
- 32
- 下标计数
- 32
- 数位分离
- 29
- 搜索
- 28
- 双分支
- 28
- 图形
- 23
- 最值
- 23
- 单分支
- 20
- 迭代
- 20
- 算法
- 20
- 前缀和
- 20
- 二维数组
- 18