C/C++教程

用C++实现数组的二分查找算法

本文主要是介绍用C++实现数组的二分查找算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

二分查找算法

原理:在使用二分查找算法之前先要确定被查找的数组必须有序的,即确定待寻找的元素的范围是[low, high],然后逐步缩小范围直到找到或找不到该元素为止。具体做法是:先取数组中间位置(mid=(low+high)/2)的数据元素与给定值比较。若相等,则查找成功;否则,若给定值比该数据元素的值小(或大),则给定值必在数组的前半部分[low,mid-1](或后半部分[mid+1,high]),然后在新的查找范围内进行同样的查找。如此反复进行,直到找到数组元素值与给定值相等的元素或确定数组中没有待查找的数据为止。因此,二分查找每查找一次,或成功,或使查找数组中元素的个数减少一半,当查找数组中不再有数据元素时,查找失败。

代码实现

#include<iostream>
#include<vector>
using namespace std;

int binarySearch(vector<int>& nums, int target) {
	int low = 0;	// low为左边界下标
	int high = nums.size() - 1; // high为右边界下标
	while (low <= high)	{ // 只要low处的元素小于等于high处的元素,说明还没查找到元素,循环继续
		int mid = (low + high) / 2; // 数组中间元素下标
		if (nums[mid] < target) { // 当所查找的元素比中间值大,说明要查找的元素在右半区	
			low = mid + 1;		// target在右半区,改变low的值
		}
		else if (nums[mid] > target) { // 当所查找的元素比中间值小,说明要查找的元素在左半区,
			high = mid - 1;		// target在左半区,改变high的值
		}
		else { // 如果前面两个条件都不满足,说明已经找到target 返回mid下标位置
			return mid;		
		}
	}
	return -1;	// 当跳出循环还没有返回值,说明没找到想要的元素,返回-1
}

void print(int i) {
	cout << i << " ";
}

int main()
{
	int target;
	vector<int> nums {15, 2, 9, 36, 78, 100, 45, 8, 24, 67}; // 定义数组
	sort(nums.begin(), nums.end());// 对数组进行排序
	cout << "排序后数组的元素依次为: "<< endl;
	for_each(nums.begin(), nums.end(), print);
	cout << endl;
	cout << "请输入你要查找的值: ";
	cin >> target;
	int index = binarySearch(nums, target);
	cout << "你所找的值排序后的下标为(-1为不存在): " << index << endl;

	return 0;
}

终端运行结果

在这里插入图片描述
在这里插入图片描述

这篇关于用C++实现数组的二分查找算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!