二分查找法

文章目录

• 二分查找法

• 二分查找的关键：

• 二分查找法演示

二分查找法

适用于有序数组，顺序查找绝大多数情况有效但是由于它是一个一个元素进行查找，其效率很低，只有一个for循环

二分查找的关键：

找到最左边元素（left）和最右边元素（right），确定中间元素（mid）

int r = 0;
	scanf("%d", &r);
	int arr[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
	int sz = sizeof(arr) / sizeof (arr[0]);
	int left = 0;
	int right = sz-1;

比较中间元素（mid）和目标元素（r）的大小，调整left和right，再确定新的mid…
接下来的问题在于怎样调整left和right的值，mid和k比较无非就三种情况：mid<r，mid>r,mid=r。第一种情况，r在mid的右边，我们将left调整为mid+1，right不用调整；第二种情况，r在mid的左边，我们将right调整为mid-1，left不用调整。最后一种情况最简单，我们已经找到了r，直接将mid打印出来就行了

int mid = (left + right) / 2;
		if (arr[mid] > r)
		{
			right = mid - 1;
		}
		else if (arr[mid] < r)
		{
			left = mid + 1;
		}
		else
		{
			printf("找到了，它是：%d", arr[a]);
			break;
		}

我们要不断确定mid直到找到r，自然需要用到循环，我们有明确的目标：找到k。因此选择while循环，找到k后循环不再进行，而当left和right之间还有元素，即left在right的左边或与之重合，k就依然可能存在，所以循环条件为left<=right，

while (left <= right)
{
}

完整代码如下：

二分查找法演示

#include <stdio.h>


int main()
{
	int r = 0;
	scanf("%d", &r);
	int arr[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	int left = 0;
	int right = sz - 1;
	while (left <= right)
	{
		int mid = (left + right) / 2;
		if (arr[mid] > r)
		{
			right = mid - 1;
		}
		else if (arr[mid] < r)
		{
			left = mid + 1;
		}
		else
		{
			printf("找到了，它是：%d", arr[mid]);
			break;
		}
	}
	return 0;

}
}