初识二分检索(BinarySearch)

二分检索的迭代与递归实现

对于该问题

在已排序好的n个元素中寻找一个特定元素x

我们可以暴力搜索,直接从0一直搜索到x,但这就和“在n个未排序的元素中寻找一个特定元素x”变得没啥区别。

所以我们需要利用“已排序”这个条件。比如先将数组分成左右两部分。假如数组是从小到大排列,那么有以下两种情况:

  • 如果x比中间元素小,那么x肯定在数组左边
  • 如果x比中间元素大,那么x肯定在数组右部
  • 如果x=中间元素,那么说明找到了x

我们可以反复进行:取中间值-与x比较-确定下一个区间-取中间值-…的操作,直到找到特定元素x或没有区间可取。这样每次我们都只对“半个数组”进行操作,

而这便是二分检索(BinarySearch)。将规模为n的问题分解为规模为k的子问题,且子问题之间相互独立并与原问题相同的这种方法也被称为分治法。

该算法可以用迭代或递归的方法实现,时间复杂度为O(logn)。

二分检索的迭代实现

通过while循环实现

我们需要先将数组分为左右两部分,那么可以用left指针指向左部的起始点,right指针指向右部的终点。再取mid=(left+right)/2为中点,它同时也是左部的终点和右部的起点。

现在思考循环什么时候终止以及具体实现。举个例子先,给定一个n=4的数组nums,假设所寻找的元素key=5

1 2 3 4

第一次分治,left=0,right=3,mid=1(在C++中int相除如果不为整,只保留整数位,不作四舍五入)。

将nums[mid]与key比较,很明显nums[mid]!=key并小于key。那么key应该在右部。

第二次分治,right指针不变。由于nums[mid]在上一次已经比较过了,不需要将它划入区间,那么left应该指向nums[mid]的下一个元素,即left=mid+1。

此时left=2,right=3,mid=2。nums[mid]仍然大于key。而数组中只剩个4没有参与进来,那么继续划分。

和上面一样,left=mid+1,right指针不变。此时发现left=right,左右指针已经同时指向区间中的最后一个元素。进行比较后发现还是不相等,那么退出循环并在屏幕上打印输出相关信息。

综上,我们可以得到二分搜索的代码:

//binarySearch
	int left = 0, right = n - 1;
	int mid;
	bool flag = false;
while (left <= right)
	{
		mid = (left + right) / 2;
		if (nums[mid] == key)
		{
			flag = true;
			break;
		}
		else if (nums[mid] < key)
		{
			left = mid + 1;
		}
		else if (nums[mid] > key)
		{
			right = mid - 1;
		}
	}

二分检索的递归实现

将重复操作化为递归

我们发现,在上面的例子中,取中间值-比较大小-取区间-取中间值的这个操作是重复的。即每次只有传入的值不一样,但对这些值的操作是一样的。

那么不如用递归来实现这个操作,和上面的迭代的实现其实差不多。比较好理解,这里直接放代码。

//binarySearch
int binarySearch(int* nums, int left, int right,int key)
{
	if (left == right)
	{
		if (nums[left] == key)
			return left;
		else
			return -1;
	}
	int mid = (left + right) / 2;
	if (nums[mid] < key)
		binarySearch(nums, mid + 1, right, key);
	else if (nums[mid] > key)
		binarySearch(nums, left, mid - 1, key);
}

完整程序实现

样例和主函数

这里提供完整程序和样例方便测试。

  • 样例输入:
    • 10 1 2 3 4 5 6 7 8 9 10
    • 20 1 11 22 33 44 55 66 77 88 99 100 123 250 500 670 780 999 1000 1024 2048
  • key值输入自取

以下则是完整代码实现

C++完整代码(迭代)

#include<iostream>
using namespace std;

int main()
{
	int n;
	cin >> n;
	int* nums = new int[n];
	for (int i = 0;i < n;i++)
	{
		cin >> nums[i];
	}
	int key;
	cin >> key;

	//binarySearch
	int left = 0, right = n - 1;
	int mid;
	bool flag = false;;
	while (left <= right)
	{
		mid = (left + right) / 2;
		if (nums[mid] == key)
		{
			flag = true;
			break;
		}
		else if (nums[mid] < key)
		{
			left = mid + 1;
		}
		else if (nums[mid] > key)
		{
			right = mid - 1;
		}
	}
	if (flag == true)
		cout << "Index:" << mid << endl;
	else
		cout << "Not Found" << endl;

}

C++完整代码(递归)

#include<iostream>
using namespace std;

int binarySearch(int* nums, int left, int right,int key)
{
	if (left == right)
	{
		if (nums[left] == key)
			return left;
		else
			return -1;
	}
	int mid = (left + right) / 2;
	if (nums[mid] < key)
		binarySearch(nums, mid + 1, right, key);
	else if (nums[mid] > key)
		binarySearch(nums, left, mid - 1, key);
}
int main()
{
	int n;
	cin >> n;
	int* nums = new int[n];
	for (int i = 0;i < n;i++)
	{
		cin >> nums[i];
	}
	int key;
	cin >> key;

	//binarySearch
	int left = 0, right = n - 1;
	int flag = binarySearch(nums, left, right, key);
	if (flag != -1)
		cout << "Index:" << flag << endl;
	else
		cout << "Not Found" << endl;
}
Subscribe
提醒
0 评论
Inline Feedbacks
View all comments
0
在此留下你的评论x