• 欢迎访问废江网站,承蒙遇见 QQ群
  • 本站将致力于推送优质的java知识以及算法,开源代码!

Binary Search

AOJ 站点默认 4年前 (2020-04-09) 4941次浏览 已收录 54个评论 扫描二维码
文章目录[隐藏]

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
喜欢 (2)
[]
分享 (0)
发表我的评论
取消评论

表情 贴图 加粗 删除线 居中 斜体 签到

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址