• 欢迎访问废江's博客 QQ群
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏本站吧

Binary Search

AOJ 站点默认 1年前 (2020-04-09) 772次浏览 已收录 76个评论
文章目录[隐藏]

Question

You are given a sequence of n integers S and a sequence of different q integers T. Write a program which outputs C, the number of integers in T which are also in the set S.

Input
In the first line n is given. In the second line, n integers are given. In the third line q is given. Then, in the fourth line, q integers are given.

Output
Print C in a line.

Constraints
n ≤ 10000
q ≤ 500
0 ≤ an element in S ≤ 109
0 ≤ an element in T ≤ 109
Sample Input 1
5
1 2 3 4 5
3
3 4 1
Sample Output 1
3
Sample Input 2
3
3 1 2
1
5
Sample Output 2
0
Sample Input 3
5
1 1 2 2 3
2
1 2
Sample Output 3
2

Meaning

使用二分搜索,效率就会很大提高。但是需要注意,二分搜索的前提是数组已经排序好了。那么排序一般最高的效率希尔排序也是0(n1.25),岂不是效率还降低了?相对于O(n),这里题目限制说了
给出的数据就是按升序排列的,那么时间复杂度就是0(qlogn)

Coding

Summary


二分搜索使用前需要对数组进行排序;
标准二分搜索算法:


个人博客 , 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权
转载请注明原文链接:Binary Search
喜欢 (0)
[]
分享 (0)
发表我的评论
取消评论

表情 贴图 加粗 删除线 居中 斜体 签到
(76)个小伙伴在吐槽
  1. There are certainly loads of particulars like that to take into consideration. That may be a great point to carry up. I provide the ideas above as general inspiration however clearly there are questions like the one you carry up where a very powerful factor might be working in trustworthy good faith. I don?t know if greatest practices have emerged round issues like that, but I am positive that your job is clearly identified as a good game. Both girls and boys feel the impression of just a moment’s pleasure, for the rest of their lives.
    匿名2021-04-12 17:15 (2天前)回复 Windows 10 | Chrome 62.0.3202.94
  2. Sorry baby
    匿名2021-04-12 13:13 (2天前)回复 Windows 10 | Chrome 62.0.3202.94
  3. best place to buy generic viagra online viagra without a doctor prescription usa viagra without a prescription
    匿名2021-04-12 10:38 (2天前)回复 Windows 7 | Chrome 83.0.4103.24
  4. pills for erectile dysfunction: erectile pills canada viagra pills
    匿名2021-04-08 09:24 (6天前)回复 Windows 10 | Chrome 83.0.4103.14
  5. ordering medicine from india: order prescription drugs from india indian online pharmacies review
    匿名2021-04-07 01:36 回复 Windows 8.1 | Chrome 83.0.4103.61
  6. Whats up are using Wordpress for your blog platform?I'm new to the blog world but I'm trying to get started and set up my own. Do you need any coding expertise to make your own blog?Any help would be really appreciated!Here is my website ... leke kremi en iyisi
    匿名2021-04-06 15:10 回复 Windows 10 | Chrome 69.0.3452.0
  7. order prescription drugs from india: online medications from india buy prescriptions from india pharmacy
    匿名2021-04-05 21:45 回复 Windows 10 | Chrome 83.0.4103.24
  8. order tetracycline online: floxin price keflex tablets
    匿名2021-04-03 21:10 回复 Windows 8.1 | Chrome 83.0.4103.61
  9. This is a great tip particularly to those fresh to the blogosphere.Simple but very precise info… Many thanks for sharing this one.A must read article!My site :: instagram aktif takipçi satın al
    匿名2021-04-03 18:06 回复 Windows 10 | Maxthon 浏览器5.2.3.2000
  10. Türkiyenin en hızlı servislerine sahip olan takipcisatinalin.org ile takipçi satın alabilir fenomen olabilirsiniz, hemen instagram takipçi almak için sitemizi ziyaret edinizAlso visit my blog post ... takipci satin al
    匿名2021-04-03 04:37 回复 Windows 10 | Chrome 67.0.3396.87
  11. generic cefixime: buy biaxin order augmentin
    匿名2021-04-02 19:30 回复 Windows 7 | Chrome 83.0.4103.61
  12. https://zithromaxproff.com/# buy cheap generic zithromax order zithromax over the counter
    匿名2021-03-30 22:49 回复 Windows 10 | Chrome 83.0.4103.0
  13. Hello i am kavin, its my first occasion to commenting anyplace, when i read this paragraph i thought i could also make comment due to this good piece of writing.My web-site; antalyaböcekilaçlama
    匿名2021-03-30 20:31 回复 Windows 10 | Chrome 66.0.3359.139
  14. instagram günümüzde en yaygın sosyal medya kullanım aracıdır, instagram da para kazanmak ve fenomen olmak için takipçi satın al işlemi yaparak günümüz de hemen fenomen olabilir, sende fenomen olmak için hemen bizimle irtibata geç
    匿名2021-03-30 14:20 回复 Windows 10 | Chrome 53.0.2785.116
  15. http://prednisonest.com/# medicine prednisone 5mg
    匿名2021-03-26 15:30 回复 Windows 8.1 | Chrome 83.0.4103.61
  16. cheap ed pills order ed pills top ed pills
    匿名2021-03-24 11:21 回复 Windows 10 | Chrome 83.0.4103.34
  17. buy prescription drugs online without ed pills online ed pills without a doctor prescription
    匿名2021-03-23 08:18 回复 Windows 10 | Chrome 83.0.4103.44
  18. mexican viagra https://viagrapills100.com/ over the counter viagra
    匿名2021-03-20 07:20 回复 Windows 8.1 | Chrome 83.0.4103.61
  19. There's definately a lot to learn about this subject. I really like all of the points you've made.my web-site; Eugene
    匿名2021-03-19 18:16 回复 Windows 10 | 未知浏览器
  20. viagra without a doctor prescription https://viagrapills100.com/ viagra amazon
    匿名2021-03-19 08:22 回复 Windows 7 | Chrome 83.0.4103.61
  21. Hi there, You have done a great job. I will definitely digg it and personally recommend to my friends. I'm sure they will be benefited from this website.Feel free to surf to my web blog :: https://wsocum.wordpress.com
    匿名2021-03-17 06:35 回复 Windows 10 | Chrome 66.0.3359.130
  22. chloroquine tablet price chloroquine tablet price
    匿名2021-03-17 06:20 回复 Windows 10 | Chrome 83.0.4096.0
  23. This is a great tip especially to those fresh to the blogosphere. Short but very accurate info… Appreciate your sharing this one. A must read post!Also visit my homepage - retinol serum
    匿名2021-03-16 17:34 回复 Windows 10 | Firefox浏览器 62.0
  24. Nice post. I learn something new and challenging on blogs I stumbleupon on a daily basis.It's always interesting to read content from other writers and practice a little something from their websites.my homepage :: haberler
    匿名2021-03-16 09:40 回复 Windows 10 | Chrome 53.0.2785.104
  25. İnstagram uygulamasında yüksek takipçisi olan hesapların yapmış olduğu paylaşımlar uygulamanın keşfet sayfasına da düşüyor,Sende keşfete düşmek için takipçi al mutlu olFeel free to surf to my homepage ... instagram takipçi satın al
    匿名2021-03-16 07:33 回复 Windows 10 | 360浏览器 SE
  26. Takipçi satın almak sadece gelir elde etmek isteyen kişilerin değil hesaplarındaki takipçi sayısını yükselterek popüler bir profil oluşturmak isteyen kullanıcılarında tercih ettikleri bir yöntemdir. Instagram fenomeni olmak için İnstagram takipçi sayınızı megatakip adresi ile güvenilir sekilde takipci alabilirsinizStop by my website ucuz takipçi satın al
    匿名2021-03-16 04:36 回复 Windows 10 | Chrome 53.0.2785.104
  27. cheap viagra online viagra discount cost of viagra
    匿名2021-03-15 22:57 回复 Windows 8.1 | Chrome 83.0.4103.61
  28. buy viagra online canada where to buy viagra online viagra price
    匿名2021-03-12 05:26 回复 Windows 8.1 | Chrome 83.0.4103.61
  29. prescription drugs online without doctor generic drugs without doctor's prescription
    匿名2021-03-10 05:56 回复 Windows 10 | Chrome 83.0.4103.61
  30. buy prescription drugs online without generic pills
    匿名2021-03-09 05:27 回复 Windows 8.1 | Chrome 83.0.4103.61
  31. tadalafil 40 mg from india: http://tadalafilonline20.com/ buy tadalafil us
    匿名2021-03-06 00:38 回复 Windows 10 | Chrome 83.0.4103.24
  32. over the counter viagra substitute walgreens viagra side effects blood pressure coupon for viagra
    匿名2021-03-01 08:22 回复 Windows 8.1 | Chrome 63.0.3239.84
  33. cialis at costco cialis pills low price cialis/dapoxetine with overnight ship
    匿名2021-02-27 18:18 回复 Windows 7 | Chrome 55.0.2883.87
  34. This is some very interesting content . Keep it up. check my news website
    匿名2021-02-26 16:37 回复 Windows 10 | Chrome 83.0.4103.61
  35. It's very effortless to find out any topic on net as compared to textbooks, as I found this post at this website.Here is my web page :: rufus download dobre programy
    匿名2021-02-18 06:23 回复 Windows 10 | Chrome 66.0.3359.170
  36. Very smooth text. free robux
    匿名2021-02-18 04:35 回复 Windows 10 | Chrome 83.0.4093.3
  37. Your site has superb material. I bookmarked the website Twyla Gonzales LaMori
    erotik2021-02-17 23:14 回复 Windows 10 | Chrome 86.0.4240.193
  38. big daddy payday loan cash advance on chase freedom card money mart payday loan without cheque
    匿名2021-02-17 22:29 回复 Windows 7 | Chrome 61.0.3163.100
  39. Hi there, I believe your web site may be having browser compatibility problems. Whenever I take a look at your site in Safari, it looks fine but when opening in Internet Explorer, it has some overlapping issues. I merely wanted to give you a quick heads up! Besides that, wonderful blog! Alidia Torin Ocko
    turkce2021-02-17 13:41 回复 Windows 10 | Chrome 86.0.4240.193
  40. This is my first time pay a visit at here and i am in fact impressed to read all at single place.| Allene Gordon Newell
    turkce2021-02-17 12:36 回复 Windows 10 | Chrome 86.0.4240.193
  41. can a payday loan garnish your wages payday loans prezi michigan payday loans laws
    匿名2021-02-17 09:59 回复 Windows 7 | Chrome 63.0.3223.8
  42. Write more, thats all I have to say. Literally, it seems as though you relied on the video to make your point. You obviously know what youre talking about, why waste your intelligence on just posting videos to your weblog when you could be giving us something informative to read? Amalia Sheppard Race
    turkce2021-02-17 02:28 回复 Windows 10 | Chrome 86.0.4240.193
  43. If some one desires to be updated with newest technologies then he must be go to see this site and be up to date everyday. Gilberte Brigg Shina
    erotik2021-02-17 02:04 回复 Windows 10 | Chrome 86.0.4240.193
  44. This is pure bliss! I need to buy the gadget to be able to make this at home. So yummy! Bambie Sampson Semmes
    turkce2021-02-17 01:28 回复 Windows 10 | Chrome 86.0.4240.193
  45. dallas hard money loans payday loan switzerland cash advance grand rapids mi hours
    匿名2021-02-14 04:03 回复 Windows 7 | Firefox浏览器 52.0
  46. viagra savings viagra onlinee best viagra alternatives
    匿名2021-02-13 17:55 回复 未知操作系统 | Firefox浏览器 34.0
  47. Very nice post. I certainly appreciate this site. Stick with it! Deny Wadsworth Corell
    erotik2021-02-13 17:53 回复 Windows 10 | Chrome 86.0.4240.193
  48. Generally I do not learn article on blogs, however I would like to say that this write-up very compelled me to take a look at and do so! Your writing taste has been amazed me. Thank you, quite nice article.| Jaclyn Feodor Carrington
    erotik2021-02-13 16:39 回复 Windows 10 | Chrome 86.0.4240.193
  49. Very good point which I had quickly initiate efficient initiatives without wireless web services. Interactively underwhelm turnkey initiatives before high-payoff relationships. Holisticly restore superior interfaces before flexible technology. Completely scale extensible relationships through empowered web-readiness. Charis Mal Cima
    erotik2021-02-13 03:17 回复 Windows 10 | Chrome 86.0.4240.193
  50. Hi there, this weekend is good in favor of me, as this time i am reading this enormous informative paragraph here at my residence. Mirilla Brannon Stephie
    turkce2021-02-12 22:57 回复 Windows 10 | Chrome 86.0.4240.193
  51. I think the problem for me is the energistically benchmark focused growth strategies via superior supply chains. Compellingly reintermediate mission-critical potentialities whereas cross functional scenarios. Phosfluorescently re-engineer distributed processes without standardized supply chains. Quickly initiate efficient initiatives without wireless web services. Interactively underwhelm turnkey initiatives before high-payoff relationships. Martie Devlen Prentiss
    erotik2021-02-12 21:40 回复 Windows 10 | Chrome 86.0.4240.193
  52. no, the latest is still 2.01 unless dlsite is behind by 2 versions, and I seriously doubt that. Camala Florian Czarra
    erotik2021-02-12 18:41 回复 Windows 10 | Chrome 86.0.4240.193
  53. Pretty! This has been an extremely wonderful post. Thank you for providing this information. Cordie Farrel Lisa
    indirmeden2021-02-12 17:54 回复 Windows 10 | Chrome 86.0.4240.193
  54. real viagra online average price of viagra legal generic viagra
    匿名2021-02-12 17:12 回复 Windows 10 | Chrome 62.0.3202.62
  55. I used Red, Aubergine, and Black in I Love This Yarn from Hobby Lobby. Hope that helps! Laverne Arturo Nataline
    indirmeden2021-02-12 14:25 回复 Windows 10 | Chrome 86.0.4240.193
  56. Heya fantastic blog! Does running a blog similar to this require a great deal of work? I have no knowledge of programming but I had been hoping to start my own blog soon. Anyway, if you have any suggestions or techniques for new blog owners please share. I understand this is off subject but I just needed to ask. Appreciate it! Harriott Barney Jordana
    yabanci2021-02-12 13:15 回复 Windows 10 | Chrome 86.0.4240.193
  57. Loved the hat and ur a good person so I guessed u would vote for joe Carmon Bailie Zaria
    erotik2021-02-12 00:43 回复 Windows 10 | Chrome 86.0.4240.193
  58. cialis diario bula pdf ocular side effects of cialis cialis nep
    匿名2021-02-11 23:51 回复 Windows 8.1 | Chrome 62.0.3202.94
  59. viagra paypal viagra online overnight shipping viagra edmonton
    匿名2021-02-11 12:35 回复 Windows 8.1 | Chrome 62.0.3202.94
  60. cash advance chase unlimited payday loans in angleton promo code ace payday loan
    匿名2021-02-11 10:26 回复 未知操作系统 | Firefox浏览器 30.1
  61. cialis kaiser cialis and zoloft interactions cialis mississauga
    匿名2021-02-11 09:20 回复 未知操作系统 | Firefox浏览器 35.0
  62. You really make it seem so easy with your presentation but I find this matter to be really something which I think I would never understand. It seems too complicated and very broad for me. I am looking forward for your next post, I will try to get the hang of it! Millisent Ozzy Neil
    amateur2021-02-10 22:40 回复 Windows 10 | Chrome 86.0.4240.193
  63. northwest pharmacy canada canadian pharmacy cialis online drugstore
    匿名2021-02-09 21:12 回复 未知操作系统 | Firefox浏览器 35.0
  64. pharmacy online store erectile dysfunction pills cheap prescription drugs
    匿名2021-02-09 15:37 回复 Windows 7 | Chrome 62.0.3202.89
  65. canadadrugsonline pharmacy near me viagra from canada
    匿名2021-02-07 07:19 回复 Windows 7 | Chrome 62.0.3202.94
  66. viagra cheapest online viagra free trial online buy viagra cheap
    匿名2021-02-05 08:17 回复 Windows 7 | Firefox浏览器 37.1
  67. viagrasites buy viagra with paypal viagra and alcohol consumption
    匿名2021-02-04 19:03 回复 Windows 7 | Firefox浏览器 56.0
  68. online pharmacy canada online pharmacy no prescription canada medication pharmacy
    匿名2021-02-04 11:17 回复 未知操作系统 | Firefox浏览器 43.1
  69. Thanks for the tips shared on the blog. Yet another thing I would like to talk about is that weight loss is not information about going on a fad diet and trying to reduce as much weight as you can in a set period of time. The most effective way in losing weight is by consuming it slowly but surely and following some basic points which can enable you to make the most from your attempt to drop some weight. You may recognize and be following many of these tips, although reinforcing know-how never damages. Joanne Wells Novia
    netflix2021-02-02 14:36 回复 Windows 10 | Chrome 86.0.4240.193
  70. wah aku ini lidah orang indonesia, banyak makanan dari luar yang gak cocok dengan lidahku , makana dari timur tengah itu biasanya kaya rempah ya Madelina Hendrik Loftis
    direk2021-02-01 12:24 回复 Windows 10 | Chrome 86.0.4240.193
  71. Hi there! Do you know if they make any plugins to protect against hackers? Josselyn Isak Elbart
    yabanci2021-02-01 06:27 回复 Windows 10 | Chrome 86.0.4240.193
  72. Maybe, but the latest polls say I am more intelligent and good looking than you by far. Robinet Porter Efram
    1080p2021-01-30 08:23 回复 Windows 10 | Chrome 86.0.4240.193
  73. Your means of describing everything in this paragraph is truly good, every one can simply know it, Thanks a lot.Also visit my page https://www.hc.com.tr/hc-leke-kremi
    匿名2021-01-26 18:13 回复 Mac OS X | Chrome 67.0.3396.62
  74. Hello there, You've done a great job. I will definitely digg it and personally recommend to my friends.I'm confident they will be benefited from this web site.my web site: logsuz shell
    匿名2021-01-26 17:37 回复 Windows 10 | Chrome 66.0.3359.66
  75. Thanks-a-mundo for the blog post. Really looking forward to read more. Want more. Delinda Aleksandr Baillie
    turkce2021-01-22 13:26 回复 Windows 10 | Chrome 86.0.4240.193
  76. I have been reading out many of your posts and i can claim pretty clever stuff. I will make sure to bookmark your blog. Guglielma Ingelbert Cohleen
    ucretsiz2021-01-12 16:57 回复 Windows 10 | Chrome 86.0.4240.193