今天重新整理了一下二分查找的内容，也可以确实说二分的东西很简单，但是想要写对二分却可以说还是一件比较难
1.查找第一个大于等于x的元素
#include <bits/stdc++.h> using namespace std; int a[11]={0,2,3,3,4,4,4,4,5,5,7}; int binary_search(int x) { int L=1,R=10; while(L<=R) { int mid=(L+R)>>1; if(a[mid]<x) L=mid+1; else if(a[mid]>=x)R=mid-1; cout<<"L"<<L<<" "<<"R"<<R<<endl;; } return L; } //寻找一个单调递增序列中大于等于x的最小的坐标 //同时若查找数字比该序列最小的数字还要小将会返回序列的第一位坐标 //需要二次判断 判断查找出来的数字是否存在于该序列（二次判断a[mid]是否等于x） int main() { cout<<binary_search(0)<<endl; }
2.寻找一个单调递增序列中等于x的最大或者小于x的坐标
#include <bits/stdc++.h> using namespace std; int a[11]={0,2,4,4,4,4,4,4,5,5,7}; int binary_search(int x) { int L=1,R=10; while(L<=R) { int mid=(L+R)>>1; if(a[mid]<=x) L=mid+1; else R=mid-1; cout<<"L"<<L<<" "<<"R"<<R<<endl;; } return R; } //寻找一个单调递增序列中等于x的最大或者小于x的坐标 //同时若查找数字比该序列最小的数字还要小将会返回序列的第一位坐标 仍要判断双边界问题 //需要二次判断 判断查找出来的数字是否存在于该序列（二次判断a[mid]是否等于x） int main() { cout<<binary_search(5)<<endl; }
3.寻找最后一个小于x的元素
#include <bits/stdc++.h> using namespace std; int a[11]={0,2,4,4,4,4,4,4,5,5,7}; int binary_search(int x) { int L=1,R=10; while(L<=R) { int mid=(L+R)>>1; if(a[mid]>=x) R=mid-1; else L=mid+1; cout<<"L"<<L<<" "<<"R"<<R<<endl;; } return R; } //寻找最后一个小于x的元素 若没有比x还小的则会返回0 //同时若查找数字比该序列最小的数字还要小将会返回序列的第一位坐标 仍要判断双边界问题 //需要二次判断 判断查找出来的数字是否存在于该序列（二次判断a[mid]是否等于x） int main() { cout<<binary_search(1)<<endl; }
4.找第一个大于x的元素的最小位置
#include <bits/stdc++.h> using namespace std; int a[11]={0,2,4,4,4,4,4,4,5,5,7}; int binary_search(int x) { int L=1,R=10; while(L<=R) { int mid=(L+R)>>1; if(a[mid]<=x) L=mid+1; else R=mid-1; cout<<"L"<<L<<" "<<"R"<<R<<endl;; } return L; } //寻找第一个大于x的元素 若溢出则被判定为找不到 //同时若查找数字比该序列最小的数字还要小将会返回序列的第一位坐标 仍要判断双边界问题 //需要二次判断 判断查找出来的数字是否存在于该序列（二次判断a[mid]是否等于x） int main() { cout<<binary_search(8)<<endl; }
原文：https://www.cnblogs.com/xyisreallycuteeee/p/14678305.html