準确實作二分查找方法

準确實作二分查找方法

    準确寫出二分查找法很重要，因為其中有許多地方容易出錯。

    主要有下面幾點：

• right初始值為num-1;
• 每次更新right=middle-1; 
• 每次更新middle為left+((right-left)>>1);  注意使用移位，以及移位運算符加括号！

正确的程式如下：

#include<iostream>
using namespace std; 

int isFinded(int *a, int num, int value)
{
	int left=0, right=num-1; 
	int middle; 

	while(left<=right)
	{
		middle=left+((right-left)>>1); 
		if(a[middle] < value)
			left=middle+1; 
		else if(a[middle] > value)
			right=middle-1; 
		else
			return middle;  //傳回找到的位置
	}

	return -1;  //沒找到
}

int main()
{
	int a[5]={1, 3, 5, 7, 9}; 
	int num=5; 
	int value=5; 

	int finded=isFinded(a, num, value); 

	cout<<finded<<endl;
	return 0; 
}