对于该问题
在已排序好的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;
}