【C/C++】折半查找（二分查找）
一、二分查找
在C和C++里，二分查找是针对有序数组所用的一种快速查找元素的方法。 在C和C++里，二分查找是针对有序数组所用的一种快速查找元素的方法。
二、二分查找的条件以及优缺点
条件：针对有序数组（元素从小到大或从大到小） 条件：针对有序数组（元素从小到大或从大到小）
优点：查询速度较快，时间复杂度为O（n） 优点：查询速度较快，时间复杂度为O（n）
缺点：有硬性条件的限制，而且即使查到后，插入与删除困难。 缺点：有硬性条件的限制，而且即使查到后，插入与删除困难。
三、图片详解
四、二分查找C语言代码块（封装后）
封装函数解释：
函数原型：binary_research(int arr[],int left , int right , int element) 函数原型：binary_research(int arr[],int left , int right , int element)
函数功能：利用二分法查找数组元素 函数功能：利用二分法查找数组元素
返回值 ：若找到元素，返回元素数组下标；否则，返回-1 返回值 ：若找到元素，返回元素数组下标；否则，返回-1
代码块：
int binary_research(int arr[],int left,int right,int element)
{
while(left<=right)
{
int mid = (left+right)/2;
if(arr[mid]>element)
{
right = mid - 1;
}
else if(arr[mid]<element)
{
left = mid + 1;
}
else
{
return mid;
}
}
return -1;
}
主函数代码块：
五、小结
二分查找对有序数组来说查询速度快。 二分查找对有序数组来说查询速度快。
优化： 优化：
可以用 可以用
int mid = left - （left - right）/2;
//防止越界 int mid = left - （left - right）/2; //防止越界
或 或
int mid = left&right+(left^right)>>1;//进行计算机最喜欢的位运算，效率略高
来代替 求两个数的平均值的操作
来代替 求两个数的平均值的操作
来代替 求两个数的平均值的操作
---------------->>>
---------------->>>
---------------->>>
----------------------->>>
下一篇：
盘点全球搜索引擎及其使用技巧