【C++】Binary Search

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

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

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

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

学习难度: ☆☆☆

#include <iostream>#include <algorithm> //内建sort的libraryusing 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