目录

题目：

方法一：不利用函数利用数组循环等求下标

 方法二：利用函数法求下标

题目：

有n个数存放在一个数组a[]中，输入一个数k，要求用折半查找求出k是数组中第几个元素的值，求该元素的下标；若k不属于数组中任何一个元素，则输出“None”。

方法一：不利用函数利用数组循环等求下标

#include<stdio.h>
int main()
{
	int a[100], k, i, mid, n, flag = 0;
	scanf("%d", &n);//输入数组的长度
	int left = 0;//首元素下标
	int right= n - 1;//末元素下标
	for (i = 0; i < n; i++)
		scanf("%d", &a[i]);//输入所有的数字
	scanf("%d", &k);//输入要查找的数字
	while (left <= right)//保证left <= right(下标)
	{
		mid = left + (right - left) / 2;//二分查找，求中间位置--注意溢出
        //mid = (left + right)/2;//未考虑溢出情况
		if (a[mid] == k)//先考虑相等的情况可以少比较两次
		{
			printf("%d\n", mid);//a[mid]=k,查找成功
			flag = 1;//查找成功flag=1
			break;
		}
		else
		{
			if (a[mid] < k)
				left = mid + 1;
			else
				right = mid - 1;
		}
	}
	if (flag == 0)//查找失败，flag仍为0（原来的数）
		printf("None\n");
	return 0;
}

先输入数组的长度（元素的个数）n，利用for循环语句随机输入n个数，再输入一个数k，若k在该数组中，在while循环语句中利用二分查找（折半查找）和if语句求元素k的下标，如果k不在该数组中，输出None，（利用flag判断k是否在该数组中）。

运行结果如下：

 方法二：利用函数法求下标

#include<stdio.h>
int binary_search(int a[], int k, int n)
{
	int left = 0;
	int right = n - 1;
	int flag = 0;
	while (left <= right)
	{
		int mid = left + (right - left) / 2;//防溢出
		//int mid = (left + right) / 2;
		if (a[mid] > k)
		{
			right = mid - 1;
		}
		else if (a[mid] < k)
		{
			left = mid + 1;
		}
		else
		{
			printf("%d\n", mid);
			flag = 1;//找到元素则flag=1
			break;//然后结束该循环
		}
	}
	if (flag == 0)//若输入的数k不在该数组中
		printf("None\n");//则输出None
}
int main()
{
	int a[100];
	int k, s, i, n;
	scanf("%d", &n);
	for (i = 0; i < n; i++)
		scanf("%d", &a[i]);
	scanf("%d", &k);//找到就返回找到位置的下标
	//数组arr传参传递的只是数组首元素的地址
	int ret = binary_search(a, k, n);
	return 0;
}

调用函数binary_search求该下标，其他方法和方法一类似

其运行结果如下：

 本来是利用调用函数方法求该下标的，后来在朋友的提醒下利用数组之前的知识求出随机值的下标，没学过函数的朋友们可以借鉴一下啦！有错误欢迎指出嘿嘿。

该方法就是找到他们的中间值，先让我们要找的值与中间值比较大小，缩小找的范围

1.寻找单个元素的准确下标

思路：主要是将区间段中二分之一的值与目标值进行比较，然后慢慢缩小区间，直至寻到目标值。

注意：此处所指的二分之一指的是数组下标，而比较的却是数组中的值。

#include<stdio.h>
int a[10]= {0,1,2,3,4,5,6,7,8,9};  
int main()
{
    int t,l=0,r=9,mid=0,ans=0; //r，l 分别代表数组的左右两端
    scanf("%d",&t);			//给定一个目标值
    while(l<=r)			   //进行循环，结束条件是当区间缩减到只有那个数时
    {
        mid=(l+r)/2;	   //下标的中间值
        if(a[mid]>t)	  //将中间值与目标值作比较
            r=mid-1;	  //如果小于，就说明目标值在中间值的左边，因此将右界限改变
        else if(a[mid]<t) //同理，大于目标值，就将左边界改变
            l=mid+1;
        else
        {
            ans=mid;    //直至寻找到目标值，终止循环
            break;
        }
    }
    printf("%d",ans);
}

	

2.寻找一个元素在数组中的初始位置和结束位置

#include<stdio.h>
int a[10]= {1,1,1,2,3,3,4,5,6,6}; //数组元素
int main() {
	int n;
	scanf("%d",&n);   //输入一个可查询的数
	int r,l,s=0,e=9,mid=0;      
	while(s<=e) {			//寻找元素左边界
		mid=(s+e)/2;		//依然是中间值比较
		if(a[mid]>=n)	   //即使寻找到n时，也继续比较，不停止
			e=mid-1;
		else
			s=mid+1;     //终止条件，当寻找到左边界时，才会出循环
	}
	l=s,s=0,e=9;		//赋值，左边界；同时归零，回到初始状态
	while(s<=e) {		//寻找右边界，理解同上
		mid=(s+e)/2;
		if(a[mid]<=n)
			s=mid+1;
		else
			e=mid-1;
	}
	r=e;
	printf("%d %d\n",l,r);//输出即可
}

_ 同是用二分查找的方法进行，这个里面用了两次，分别寻找左右边界。
与案例一不同的是，案例一中寻找到所需要的值即可跳出循环；但是，案例二中不同的是，即使寻找到了，也不停止，直至寻找到边界为止，（可见代码中的>=和<=）。
此时，循环会执行到左边界左边的值和右边界右边的值，就会跳出循环，输出就找到啦 _