DAY3 二分查找
一、二分查找是什么？
在一个有序的集合中，每次寻找中间的数并与需要寻找的数字进行比较从而缩小范围。
这样每一次都可以缩小一半的范围
二分查找的优点是时间复杂度为O(logn)，在数据量巨大的时候，可以大幅缩小时间。
提示： 需要注意的是所寻找的数字必须在一个有序的集合中，才能保证二分查找能够查到
二、使用步骤
1.大致模板
使用时根据需要进行变换
代码如下（示例）：
int bfound(int key)
{
int start = a,end = b;
while(start <= end)
{
int mid=(start + end) >> 1;
if(mid == key)
{
return 1;
}
else if(mid <= key)
{
start = mid + 1;
}
else
{
end = mid - 1;
}
}
}
2.变式
不仅仅在有序集合中寻找相应数字时需要用到二分查找，有时候面对一些复杂的问题需要我们找出答案的题目，可以通过对答案在答案可能出现的范围内进行二分查找。对答案二分查找后经行判断搜索出的答案是否符合要求在经行上下调动答案的范围。
问题如下（示例）：
Defuse the Bombs
The terrorists have planted some bombs in a building! Our hero, Little Horse, decides to rescue the people in the building. Unfortunately, there is more than one bomb, and Little Horse is unable to defuse all of them. To strive for more time for other people to escape, Little Horse decides to sacrifice himself.
There are n bombs in the building, each of which has a countdown clock. In the beginning, the i-th bomb’s clock is set to ai. Then:
Little Horse chooses one bomb, making its clock increase by 1.
Every bomb’s clock decreases by 1.
If at least one clock becomes lower than 0, all the bombs will explode. Otherwise, go back to step 1.
Obviously, the explosion is not avoidable. What a sad story. But Little Horse doesn’t care about his survival now. He just wants to strive for more time. So can you tell him how many times he can do step 1 at most before the explosion?
Input
The first line of the input contains an integer T (1≤T≤100) — the number of test cases.
The first line of the input contains an integer n (2≤n≤105) — the number of bombs. The sum of n will not exceed 3×105.
The next line contains n numbers a1,a2,…,an (0≤a1,a2,…,an≤109) — the clocks of the bombs in the beginning.
Output
For the x-th test case, if the answer is y, output Case #x: y in a single line.
Example
Input
2
2
1 1
3
1 2 3
Output
Case #1: 3
Case #2: 4
代码如下（示例）：
long long a[1000005] = { 0 };
int time(int n)
{
long long start = 0, end = INT_MAX;
while (start <= end)
{
long long mid = (start + end) >> 1;
long long sum = 0;
for (long long i = 0; i < n; ++i)
{
if (a[i] - mid < 0)
{
sum += (mid - a[i]);
}
}
if (sum <= mid)
{
start = mid + 1;
}
else
{
end = mid - 1;
}
}
return start;
}
int main()
{
int T, n;
scanf("%d", &T);
for (int j = 1; j <= T; ++j)
{
scanf("%d", &n);
for (int i = 0; i < n; ++i)
{
scanf("%d", &a[i]);
}
sort(a, a + n);
printf("Case #%d: %d\n", j, time(n));
memset(a, 0, sizeof a);
}
return 0;
}
总结
二分查找可以将查找的内容的时间复杂度从O(n)变成O(logn)
但是需要被查找的内容一定要是属于一个有序的数组中
https://vjudge.net/contest/418909