二分搜索(BinarySearch)是基于分治算法的一种搜索算法,最简单的版本是用来查找某个数是否在数组里

下面举个栗子说明一下~~

输入:数组 a,下标从left至right,数字x

输出:若x在数组a中,就输出其下标,否则输出no answer

基本思想:1、首先数组是有序的(从小到大)

                 2、将x与数组中间值a[mid]比较

                 3、若x>a[mid],说明x只可能在后一半的数组里,对后一半数组进行递归;

                      若x<a[mid],取前一半数组进行递归

                 4、通过不断的递归操作后,子问题最终递归至仅有一个元素a[ ],将x与a[ ]进行比较即可

代码实现:

#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;
//这个算法仅适用于有序序列
int a[1000];
int BinarySearch(int a[], int left, int right, int x)
{
	int mid;
	mid = (left + right) / 2;
	while (left < right) {
		if (x == a[mid])
			return mid;
		else if (x < a[mid])
			return BinarySearch(a, left, mid - 1, x);//递归调用前一半数组
		else
			return BinarySearch(a, mid + 1, right, x);//。。。后一半。。。
	}
	return 0;
}
int main()
{
	int x, n, flag = 0;
	cin >> x >> n;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	flag = BinarySearch(a, 1, n, x);
	if (flag)
		printf("%d", flag);
	else
		printf("no answer");
	return 0;
}