【C++】Binary Search

Binary Search 是一个搜寻演算法~ 它的时间复杂度只有O log(n)~

但使用它之前要先确认资料是已排序过的~

在使用回圈将 target 与中间值比较，如 target 大於中间值，就往右搜寻~ 否则就往左搜寻~

学习目标: Binary Search的概念及实务

学习难度: ☆☆☆

#include <iostream>

#include <algorithm> //内建sort的library

using namespace std;

int BinarySearch(int array[],int length,int target)
{
	int start,end,mid;
	
	start=0;
	
	end=length-1;
	
	while(start<=end)
	{
		mid=(start+end)/2;
		
		if(array[mid]==target)
		{
			return ++mid;
		}
		else if(target>array[mid])
		{
			start=mid+1;
		}
		else if(target<array[mid])
		{
			end=mid-1;
		}
	}
}

int main()
{
	int array[8]={12,3,1,5,18,10,7,35};
	
	int length=sizeof(array)/sizeof(array[0]); /*array的长度是array的大小除以单一元素的大小*/
	
	sort(array,array+length); /*可以先用内建的sort，如果没用其他排序*/
	
	int target=BinarySearch(array,length,7);
	
	cout<<target<<endl;
		
	return 0;
}

参考资料:

https://shengyu7697.github.io/cpp-binary-search/

https://www.google.com/search?q=binary+search+c%2B%2B&source=hp&ei=YqdRYvXZObCymAW0rL7oBQ&iflsig=AHkkrS4AAAAAYlG1cnO1ZSUym6ofO_RVje6d3oMkYtUZ&oq=Binary+Search&gs_lcp=Cgdnd3Mtd2l6EAEYAjIICAAQgAQQsQMyCAgAEIAEELEDMgUIABCABDIFCAAQgAQyBQgAEIAEMgUIABCABDIFCAAQgAQyBQgAEIAEMgUIABCABDIFCAAQgARQAFgAYO8HaABwAHgAgAE3iAE3kgEBMZgBAKABAqABAQ&sclient=gws-wiz