有序数组中找到num

问题

在有序数组中找到num。

分析

直接遍历查找均可。但既然是有序数组，则充分利用此条件，采用效率更高的二分法。

代码

创建一个随机的有序数组

void Random_array(int* array, int num)
{
	for (int i = 0; i < num; i++)
		array[i] = rand() % 100;
}

void Print_array(int* a, int n)
{
	for (int i = 0; i < n; i++)
		printf("%d ,", a[i]);
	printf("\n");
}

void swap(int& a, int& b)
{
	int temp = a;
	a = b;
	b = temp;
}
void Bubble_sort(int* a, int n)
{
	if (n < 2)
		return;
	for (int i = n - 1; i >= 0; i--)
	{
		for (int j = 0; j < i; j++)
		{
			if (a[j] > a[j + 1])
				swap(a[j], a[j + 1]);
		}
	}
}

使用遍历查找，用于后续测试二分法是否正确

bool isIn_1(int array[], int num)
{
	//for (int i = 0; i < sizeof(array) / sizeof(array[0]); i++)
	for (int i = 0; i < N; i++)
		if (array[i] == num)
			return true;
	return false;

}//遍历查找，笨方法

二分法

简而言之，对比查找的num，与中间的数比较大小，然后取数组一半，再去这段数组和中间值作比较，循环往复。

bool isIn_2(int array[], int num)
{

	//int mid,L = 0, R = sizeof(array) / sizeof(array[0]);
	int mid = 0, L = 0, R = N - 1;
	while (L <= R)
	{

		mid = (L + R) / 2;
		if (array[mid] == num)
			return true;
		else if (num > array[mid])
			L = mid + 1;
		else
			R = mid - 1;

	}
	return false;
}

测试代码

随机生成数组，调用两个方法，查看结果是否一致。

完整代码

//P17 二分法查找有序数组数组中的指定数值
#include <iostream>
using namespace std;
#define N 30
void Random_array(int* array, int num)
{
	for (int i = 0; i < num; i++)
		array[i] = rand() % 100;
}

void Print_array(int* a, int n)
{
	for (int i = 0; i < n; i++)
		printf("%d ,", a[i]);
	printf("\n");
}

void swap(int& a, int& b)
{
	int temp = a;
	a = b;
	b = temp;
}
void Bubble_sort(int* a, int n)
{
	if (n < 2)
		return;
	for (int i = n - 1; i >= 0; i--)
	{
		for (int j = 0; j < i; j++)
		{
			if (a[j] > a[j + 1])
				swap(a[j], a[j + 1]);
		}
	}
}



//判断数组中是否有此数
bool isIn_1(int array[], int num)
{
	//for (int i = 0; i < sizeof(array) / sizeof(array[0]); i++)
	for (int i = 0; i < N; i++)
		if (array[i] == num)
			return true;
	return false;

}//遍历查找，笨方法

bool isIn_2(int array[], int num)
{

	//int mid,L = 0, R = sizeof(array) / sizeof(array[0]);
	int mid = 0, L = 0, R = N - 1;
	while (L <= R)
	{

		mid = (L + R) / 2;
		if (array[mid] == num)
			return true;
		else if (num > array[mid])
			L = mid + 1;
		else
			R = mid - 1;

	}
	return false;
}


int main()
{
	srand((unsigned int)time(NULL));
	for (int j = 0; j < 1000000; j++)
	{
		int array[N] = {};
		Random_array(array, N);
		Bubble_sort(array, N);
		if (isIn_1(array, 66) == isIn_2(array, 66))
			cout << "对";
		else
		{
			Print_array(array, N);
			cout << isIn_1(array, 66) << endl;
			cout << isIn_2(array, 66);
			break;
		}
	}
	//int array[N] = {};
	//Random_array(array, N);
	//Print_array(array, N);
	//Bubble_sort(array, N);
	//Print_array(array, N);
	//cout << isIn_1(array, 66) << endl;
	//cout << isIn_2(array, 66);
	return 0;
}