首页 > 试题广场 >

二分查找

[编程题]二分查找
  • 热度指数:468 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 64M,其他语言128M
  • 算法知识视频讲解
请实现有重复数字的有序数组的二分查找。
输出在数组中第一个大于等于查找值的位置,如果数组中不存在这样的数,则输出数组长度加一。

输入描述:
第一行两个正整数 nv,分别表示数组长度与查找值。

第二行 n 个正整数 a_i,表示有序数组。

1 \le n,v \le 10^5
a_1 \le a_2 \le a_3 \le ... \le a_n \le n


输出描述:
输出在数组中第一个大于等于查找值的位置,如果数组中不存在这样的数,则输出数组长度加一。
示例1

输入

5 4
1 2 4 4 5

输出

3
示例2

输入

5 4
1 2 3 3 5

输出

5
示例3

输入

5 4
1 2 2 3 3

输出

6