二分法实现一个整形有序数组的二分查找

             二分法实现一个整形有序数组的二分查找

          二分法可以提高整个程序的效率，一个有序的数组实现查找，二分法无疑是最好的方法了。

        设查找的数为key，若有序数组中间的元素比num大，则在前半部分查找，反之在后半部分查找，据此循环。如果相等，则循环结束，输出下标。   

下面简单举例：

#define _CRT_SECUSE_NO_WARNINGS 1
#include<string.h>
#include<stdio.h>
#include<iostream>
int binary_search(int arr[], int key, int sz)
{
	int left = 0; int right = sz - 1;
	while (left <= right)
	{
		int mid = left +((right - left) / 2);
		if (arr[mid] > key)
			right = mid - 1;
		else if (arr[mid] < key)
			left = mid + 1;
		else
			return mid;
	}
	return -1;
}	  
int main()
{
	int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
	int key = 6;
	int sz = sizeof(arr) / sizeof(arr[0]);
	int ret = binary_search(arr, key, sz);
	if (ret == -1)
		printf("没找到\n");
	else
		printf("%d\n", ret);
	system("pause");
	return 0;
}

如果知道大概的范围，可以改变一下参数，将这个范围的下标传过去，比如：

#define _CRT_SECUSE_NO_WARNINGS 1
#include<string.h>
#include<stdio.h>
#include<iostream>
int binary_search(int arr[], int key, int left,int right)
{
	//int left = 0; int right = sz - 1;
	while (left <= right)
	{
		int mid = left + ((right - left) / 2);
		if (arr[mid] > key)
			right = mid - 1;
		else if (arr[mid] < key)
			left = mid + 1;
		else
			return mid;
	}
	return -1;
}
int main()
{
	int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
	int key = 6;
	int ret = binary_search(arr, key, 2,8);
	if (ret == -1)
		printf("没找到\n");
	else
		printf("%d\n", ret);
	system("pause");
	return 0;
}

这样可以减少循环次数。

运行结果如下：