C语言——二分查找

【前置】多个字符从两端移动，向中间汇聚

利用代码实现如下效果：

############
H##########!
He########d!
Hel######ld!
Hell####rld!
Hello##orld!
Hello world!

要求：

刚开始全部是 ############ ，每循环一次，左右两边各一个#被代替成 Hello world! 这句话

的对应字符

思路：

1.需要创建两个数组来存储原始字符串 ############ 和用来替代的字符串 Hello world!

2.需要计算数组的长度从而计算原始字符串哪个位置对应替代字符串的位置

隐藏条件：两个数组的长度相同

因此只需要计算一个数组的长度即可，同时数组存储的是字符串，可以使用 strlen()函数计算长度，strlen()函数计算字符串长度时不会计算最后的终止符 \0

也可以使用 sizeof(arr)/sizeof(arr[0]) 来计算数组的长度，但字符串在存储的过程中会添加终止符 \0，而 sizeof(arr)/sizeof(arr[0]) 在计算时会把终止符计算进去，所以数组的真实长度为 sizeof(arr)/sizeof(arr[0])-1

3.需要两个变量 left 和 right 来代表左右两边移动的位置（即移动到哪里了）

int left = 0;
int right = strlen(arr)-1;
//数组的下标是从0开始，最后一个元素的下标是数组的长度-1
//如果是用sizeof(arr)/sizeof(arr[0])来计算长度的话，最后一个元素的下标是sizeof(arr)/sizeof(arr[0])-2
//在DEV——C++中使用strlen()函数时需要包含头文件#include <cstring>

完整实现代码如下：

#include <stdio.h>
#include <cstring>
int main()
{
	char arr1[] = "Hello world!";
	char arr2[] = "############";
	int left = 0;
	int right = strlen(arr1)-1;
	while(left<=right)
	{
		printf("%s\n",arr2);
		arr2[left] = arr1[left];
		arr2[right] = arr1[right];
		left++;
		right--;
	}
	printf("%s",arr2);
	return 0;
}

二分查找：

可以运用二分查找的前提条件：必须有序

二分查找的思路和前置问题有点像但有不同，会多一个变量 mid 作为比较值

假设我要在 [1,2,3,4,5,6,7,8]里面找到数字5，利用二分查找的思路如下：

int sz = sizeof(arr)/sizeof(arr[0]);
int left = 0;
int right = sz-1;
int mid = left+(right-left)/2;

第一次比较：mid指向的 arr[3]（即数字4）和5比大小，因为4比5小，因此我想要找的数字就在4的左边（相当于 arr[0] 到 arr[3] 都已经找过了，都比数字5小），此时重置 left 的值，将 left 变为 mid+1(因为 mid 所指的数字和我想找的数字已经比较了，再比较一次没有意义)

第二次比较：因为第一次比较后 left 的值发生变化，而 mid=left+(right-left)/2 ，所以 mid 也会发生变化

此时 mid 指向的是 arr[5] (即数字6) 和5比大小，因为6比5大，因此我想要找的数字就在6的右边，此时重置 right 的值（相当于 arr[5] 到 arr[7] 都已经找过了，都比数字5大），将 right 变为 mid-1(因为 mid 所指的数字和我想找的数字已经比较了，再比较一次没有意义)

第三次比较：

此时 mid 指向的是 arr[4] (即数字5) 和5比大小，相等即找到了数字5

如果此时还没有找到我想要的数字，那么要么 right 会变成 mid-1 ，要么 left 会变成 mid+1 ，无论哪种情况， left 都会大于 right ，一旦 left > right 就证明整个数组已经全部找过了，如果还没有找到，证明不在想找的数字不在这个数组里面

完整的代码如下：

#include <stdio.h>
int main()
{
	int arr[10] = {0};
	int sz = sizeof(arr)/sizeof(arr[0]);
	int i = 0;
	int num = 0;
	int left = 0;
	int right = sz-1;
	int mid = (left+right)/2;
	int flag = 0;
	//数组必须有序 
	for(i=0;i<sz;i++)
	{
		scanf("%d",&arr[i]);
	}
	printf("请输入要查找数字的值，我将返回对应数字的下标：————>"); 
	scanf("%d",&num);
	
	while(left<=right)
	{
		if(arr[mid]<num)
		{
			left = mid+1;
		}
		else if(arr[mid]>num)
		{
			right = mid-1;
		}
		else
		{
			flag = 1;
			break;
		}
		mid = (left+right)/2;
	}
	if(flag)
	{
		printf("数字%d对应的下标是%d",num,mid);
	}
	else
	{
		printf("数字%d不存在",num);
	}
	return 0;
}