c语言二分查找

二分查找

• 1.左闭右闭区间
• 2.左闭右开区间

写二分查找的时候每次都犹犹豫豫，修修改改，总是写不好，所以想想着磨刀不误砍柴工，静下来好好研究一下平时看起来很简单的算法.

• 二分查找适用找有顺序的数据，可以是递增的，也可以是递减的
• 二分查找的时间复杂度，最好的情况是一次找到，o(1)，最坏的情况是一直一直折半直到只剩一个元素，第一次N/1，第二次N/2，…N/2^x=1，所以x=log2N。
  

  
  

  所以最差的情况就是o(log2N)。
  

  
  

1.左闭右闭区间

int  a[10]={1,2,3,4,5,6,7,8,9,10};    //定义一个数组
int left=0;  //左端点 
int right=9;    //右端点
//所谓的左闭右闭区间就是指在一个**完全闭合**的区间找目标值(target)
//如果比如我要在区间[0,9]找target==4的数组下标，很显然这里答案是3.
//下面用代码说明

#include
int main()
{
	int a[10]={1,2,3,4,5,6,7,8,9,10};
	int left=0;    //左区间
	int right=sizeof(a)/sizeof(int)-1;    //右区间
	int target=4;
	while(left<=right)
	{
		int middle=(left+right)/2;
		if(a[middle]>target)   //如果中点大于目标值，那么就说明目标值在中点前面，且不等于中点
			right=middle-1;
		else
			if(a[middle]<target)//如果中点大于目标值，那么就说明目标值在中点后面，且不等于中点
				left=middle+1;
		else     //a[middle]==target  ,,找到该target，输出并退出while循环
		{
			printf("目标值的下标：%d",middle);
			break;
		}
	}
	if(left>right)
		printf("没有找到");
	return 0;
}

为什么这里的while循环条件是’‘left<=right’'，而不是"left

2.左闭右开区间

顾名思义，左闭右开区间就是[left,right);  要在区间[left,right)中找到target
比如要在区间[0,9)找到target。


(1)if (a[middle] > target) right 更新为 middle，因为当前a[middle]不等于target，去左区间继续寻找，而寻找区间是左闭右开区间，所以right更新为middle，即：下一个查询区间不会去比较nums[middle]
(2)while (left < right)，这里使用 < ,因为left == right在区间[left, right)是没有意义的

#include
int main()
{
	int a[10]={1,2,3,4,5,6,7,8,9,10};
	int target = 3;
	int left = 0;
	int right = sizeof(a) / sizeof(int)-1;
	while (left < right)
	{
		int middle = (right + left) / 2;
		if (a[middle] > target)
			right = middle;    //不是right=middle-1
		else
			if (a[middle] < target)
				left = middle + 1;
			else
			{
				printf("目标原素的下标是:%d", middle);
				break;
			}
	}
	if (left >= right)
		printf("没有找到该元素!");
	return 0;

}

建议把有开区间的情况转换成全是闭区间，for example:要找区间[0,9）的target, 实际上就是找[0,8]的target,因为下标为9的数是不在区间的.这样全部都用while(left<=right）作为循环条件