二分查找法的实例分析

二分查找：折半查找，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如                     果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置                     记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以                    上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。

优点：比较次数少，查找速度快，平均性能好

缺点：要求待查表为有序表，且插入删除困难

时间复杂度：O(log n)

二分查找分析：

      （1）左闭右闭式

       （2）左闭右开式

二分查找实现：

     BinarySearch.h:

#pragma once

#include <assert.h>

//左闭右闭式
int BinarySearch(int *Array, int x,size_t size)
{
	assert(Array);
	int left = 0;
	int right = size - 1;
	
	while (left <= right)
	{
		int mid = left + (right - left) / 2;  
		//没有写成mid = (left + right) / 2是为了防止整数溢出
		if (x < Array[mid])
		{
			right = mid - 1;
		}
		else if (x > Array[mid])
		{
			left = mid + 1;
		}
		else
		{
			return Array[mid];
		}
	}
	return -1;   //返回 -1 表示没有找到
}

//左闭右开式
int BinarySearch(int *Array, int x, size_t size)
{
	assert(Array);

	int left = 0;
	int right = size;

	while (left < right)
	{
		int mid = left + (right - left) / 2;   
		//没有写成mid = (left + right) / 2是为了防止整数溢出
		if (x < Array[mid])
		{
			right = mid;
		}
		else if (x > Array[mid])
		{
			left = mid + 1;
		}
		else
		{
			return Array[mid];
		}
	}
	return -1;   //返回 -1 表示没有找到
}

我在这里直接返回了找着到的数值，而没有返回其在数组中的下标，没有找到责返回 -1

Test.cpp:

#define _CRT_SECURE_NO_WARNINGS 1

#include <stdio.h>
#include <stdlib.h>

#include "BinarySearch.h"

int main()
{
	int Num[] = { 1,3,4,6,8,9,23,65,68,89,234,678,890 };
	int ret = 0;
	int size = 0;
	ret = BinarySearch(Num,25,sizeof(Num)/sizeof(Num[0]));
	if (ret < 0)    //也就是返回 -1 ,表示没有找到
	{  
		printf("This value is inexistence!\n");
	}
	else    //找到的直接返回其数值
	{
		printf("ret = %d\n", ret);
	}
	system("pause");
	return 0;
}

存在不足还望多多指教！

本文出自 “CLOWN” 博客，请务必保留此出处http://clown5.blog.51cto.com/10730975/1757249

二分查找法的实例分析

原文：http://clown5.blog.51cto.com/10730975/1757249