当前位置：首页 > article >正文

计算机算法分析与设计（23）---二分搜索算法(C++)

article 2024/10/27 10:21:18

文章目录

1. 算法介绍
2. 代码编写

1. 算法介绍

1. 二分搜索（英语：binary search），也称折半搜索（英语：half-interval search）、对数搜索（英语：logarithmic search），是用来在一个有序数组中查找某一元素的算法。

2. 二分搜索算法基本思想是：将 $n$ 个元素分成个数大致相同的两半，取 $a [n /2]$ 与 $x$ 作比较。如果 $x = a [n /2]$ ，则找到 $x$ ，算法终止；如果 $x < a [n /2]$ ，则在数组 $a$ 的左半部分继续搜索 $x$ ；如果 $x > a [n /2]$ ，则在数组 $a$ 的右半部分继续搜索 $x$ 。

3. 与普通查找比较验示，发现二分查找可以有效降低查找次数。

在这里插入图片描述

4. 数组长度为奇数和偶数的情况，这里我们用最大角标来除。

在这里插入图片描述

2. 代码编写

#include<iostream>
#include<algorithm>
using namespace std;
int n, x, a[105];
int bs(int left, int right, int x){
	int mid = (left + right) / 2;
	if (x < a[mid])
	{
		return bs(left, mid - 1, x);
	}
	else if (x > a[mid])
	{
		return bs(mid + 1, right, x);
	}
	else
	{
		return mid;
	}
}
int main(){
	cout<<"请输入元素个数："<<endl;
	cin >> n ;
	cout<<"请输入数组元素："<<endl;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	cout<<"请输入查找元素："<<endl;
	cin >> x;
	 
	sort(a,a+n);  //升序排列 
	cout<<"该查找元素在排序后数组中的角标为："<<endl;
	cout << bs(0, n-1, x);
	return 0;
}