二分查找，也称折半查找，用于在有序数组中查询特定元素。
二分查找的情形不止一种，而是有三种，分为以下情况：
- 查找数值，只要找到对应的值即可。
- 查找左侧边界，针对查询元素存在重复的情况，查找左侧出现的第一个位置。
- 查找右侧边界， 同上。
数值查找：
// 查找数组a中val的出现位置
int binary_search(int a[], int n, int val) {
int ret = -1; // 查找失败返回-1
int left = 0;
int right = n - 1;
int mid;
while(left <= right) {
mid = left + (right - left) >> 1; // 防止直接平均可能的溢出问题
if(a[mid] < val) {
left = mid + 1;
} else if(a[mid] > val) {
right = mid - 1;
} else { // 相等情况放到最后，减少分支预测，因为多数搜索情况不是大于就是小于
ret = mid;
break;
}
}
return ret;
}
查找左边界：
查找右边界：