# 二分 ## 简述 二分法也叫二分查找,是在**有序**数组中进行的一个查找操作，在这里我强调有序 我们假设一个情景：你要在一个数组中查找一个数是否存在，你会怎么办，最简单的想法是用for 循环遍历一遍如果存在返回 1 否则返回 0 ，这种情况当然很简单但是如果 数组种的数太多的话，列入这个数组有 1 亿个数用for 循环的复杂度是 O(n) , 这种情况下在算法竞赛中是不可能通过的，因此我们在这里引入二分的用法： ## 基本思想 对于一个数组 arr[] = [ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 ] 我们用二分法如何查找其中的 6 呢？ 我们需要三个辅助变量 int low = 1 , upper = 9 ; int mid = (low + upper) / 2 (5) ; 如果 low <= upper 此时 arr[mid] < 6 则 low= mid + 1 , mid = (low + upper ) / 2 (7); 如果 low <= upper 此时 arr[mid] > 6 则 upper = mid - 1 , mid = (low + upper) / 2 (6) ; 如果 low <= upper 此时 arr[mid] = 6 ; 则 low = mid + 1 ,mid = (low + upper ) / 2 (6) ; 此时low > upper结束循环 程序如下： ``` #include <bits/stdc++.h> using namespace std; int main() { int arr[11] = { 0 ,1 ,2 ,3 ,4 ,5 ,6 ,7 ,8 ,9 } ; int low = 1,upper = 9,mid ; while ( low <= upper ) { mid = (low + upper) / 2 ; if ( arr[mid] <= 6 ) { low = mid + 1 ; } else { upper = mid - 1 ; } } printf("%d\n",arr[mid]) ; return 0; } ``` ## 当然二分的用法不仅于此 你或许认为有序这个条件有些难以达到，但是二分确实是一个非常强有力的工具 接下来给大家介绍一系列题目大家做一下感受一下，可能其中有很多其他的想法 [Stages](https://vjudge.net/problem/CodeForces-1011A) [They Are Everywhere](https://vjudge.net/problem/CodeForces-701C) [The Frog's Games](https://vjudge.net/problem/HDU-4004) [Trailing Zeroes (III)](https://vjudge.net/problem/LightOJ-1138) [Pie](https://vjudge.net/problem/HDU-1969) [Sweet Journey](https://vjudge.net/problem/HDU-5477) [pairs](https://vjudge.net/problem/HDU-5178)