目录

第十单元 查找与检索

10.1 顺序查找

10.2 二分查找!

(1) 普通的二分查找（非递归）

(2) 二分查找求下界

(3) 二分查找求上界

---

第十单元 查找与检索

10.1 顺序查找

int find(int *a, int x, int y, int v)
{
for (int i=x; i<=y; i++)
if (a[i]==v) return true;
return false;
}

10.2 二分查找!

注意：
 必须使用顺序存储结构，不能使用链表。
 要查找的线性表必须是有序的。
 一般情况下，“使最大值最小”和数以十万计的数据规模暗示着你：问题要用二分法解决。

(1) 普通的二分查找（非递归）

将在 a 的区间[x,y)内寻找 v。

int bsearch(int *a, int x, int y, int v)
{
while (x<y) // 注意：不要写成“x<=y”，否则会死循环！
{
int mid=x+(y-x)/2;
if (v==a[mid]) 
return mid;
else if (v<a[mid])
y=mid;
else
x=mid+1; // 注意：不要忘记加1！
}
return -1; // 找不到
}

(2) 二分查找求下界

下面函数会寻找 a 的区间[x,y)中大于等于 v 的第一个数，使得 v 插入到 a 中对应位置，然后 a 还是一个有序的数组

int lower_bound(int *a, int x, int y, int v)
{
while (x<y)
{
int mid=x+(y-x)/2;
/*
v==a[mid]：至少找到一个，但前面可能还有。
v<a[mid]：不能在mid的后面
v>a[mid]：mid和前面都不可以。
*/
if (v<=a[mid]) y=mid; else x=mid+1;
}
return x;
}

(3) 二分查找求上界

函数应该寻找寻找 a 的区间[x,y)小于等于 v 的最后一个数，使得 v 插入到 a 中对应位置，然后 a 还是一个有序的数组。
只需对(2)中代码进行如下修改：

int upper_bound(int *a, int x, int y, int v)
{
while (x<y)
{
int mid=x+(y-x)/2;
/*
v==a[mid]：至少找到一个，但右边可能还有。
v<a[mid]：mid和后面都不可以。
v>a[mid]：不能在mid的前面。
*/
if (v>=a[mid]) x=mid; else y=mid-1;
}
return y;
}