搜索算法2：C语言二进制搜索实现

二进制搜索是一种适用于排序数组的简单搜索技术，可以是升序或降序。

以下是执行二进制搜索的步骤：

1. 二进制搜索可以类似于在字典中搜索单词。我们在中间打开这本书，并检查是否找到了名称。
2. 如果找不到该单词，则根据获得的结果，我们倾向于前进或后退。
3. 如果找到了该词，那么我们将采用该词的含义。

程序设计：

程序设计非常简单。

1. 我们认为第一个元素为低，最后一个元素为高。即应该对数组进行排序。
2. 我们使用以下公式获得中间元素的索引：
   2. 中=（低+高）/ 2。
3. 然后，我们将中间元素的值与键进行比较，如下所示：
   1. 如果（key == a [mid]）返回中。
4. 假设如果在该索引中找不到该键，则我们检查该键是低于还是高于中间值。假设键值较低，则将高值更改为中间元素，然后重复步骤1。

If(key < a[mid])
	High = mid -1
Else
	Low = mid + 1

借助示例了解二进制搜索：

基本上从上面的解释来看，将有3种情况。

情况1： 当键== array [mid]时。在这种情况下，我们退出循环

情况2： 当键>数组[mid]。在这种情况下，我们将移至数组的右半部分。

Case3: 当键<数组[mid]。在这种情况下，我们向数组的左半部分移动。

例：

Consider the sorted array 
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
key = 2

First Pass: 
	[8/2] = 4
	is arr[4] == 2 ? No, and 2 < 5. Hence discard right half and move towards left half.

Second Pass: 
	[3/2] = 2
	is arr[2] == 2 ? No, and 2 < 3. Hence discard right half and move towards left half.

Third Pass: 
	[1/2] = 1
	is arr[1] == 2 ? Yes, hence our result.

用于二进制搜索的C代码：

#include<stdio.h>

void binary_Search(int *array, int len, int key)
{

	int i = 0;

	int min_index = 0;
	int max_index = len-1;

	while(min_index <= max_index) 
	{
		// calculate the mid index
		int mid = (min_index + max_index) / 2;
		printf("mid = %d\n",array[mid] );
		// check if we get the key
		if(array[mid] == key) 
		{
			printf("Key has been found\n");
			return; 
		}

		// traverse in the right side
		else if(array[mid] < key) 
		{
			min_index = mid + 1;
		}
		// traverse in the left side
		else 
		{
			max_index = mid - 1;
		}
	}

	printf("Not able to find key\n");

}

int main()
{
	int arr[5] = {10, 30, 45, 48, 78};

	int arrayLen = 5;

	int key = 45;

	int key_2 = 34;

//successful search
	binary_Search(arr,arrayLen, key);

//key not found case
	binary_Search(arr,arrayLen, key_2);

return 0;
}

对于二进制搜索，在最坏情况下的运行时间：

在最坏的情况下，我们从n减少到n / 2

n / 2至n / 4

n / 4到n / 8，我们减少直到达到1。

因此n / 2 ^ k = 1

K = log n。

因此，在最坏的情况下， [log n].

进一步阅读：

AJ关于DS和算法的权威指南。单击此处以学习算法和数据结构教程的完整列表。 85多个章节可供学习。

该网站上可用的教程列表：