「data structure」的圖片搜尋結果

數據結構外傳(一) : 二分查找法

二分查找法式大家最熟悉,的查找方式之一,運行效率也非常快,時間複雜度為O(logN),下面就簡單介紹一下吧!

舊台北 1948

介紹前我先說個故事,在電話還未普及前,遠距離溝通除了飛鴿傳書外,還有就是發電報 !! 但以往電報纜線材質很差,時常中間斷了,電報工人最頭痛的就是要到底斷在哪裡。

國道三號(找不到電報圖)

今天有一個從台北到高雄的電報纜線,今天一個颱風,斷了!! 電報工人該如何尋找斷裂處?

  1. 從台北往南走一個一個檢查。簡直太笨了,萬一斷在高雄則不是要檢查一個月,從台北走到高雄才檢查得出來。
  2. 二分搜尋,我派人在台中往台北發電報,假設通了,代表斷在台中以南 ; 假設不通,代表斷在台中以北。如果斷在台中以北,則在桃園打個電話,向北向南打,如果桃園打到台中不通,代表斷在這之間。

同理可以得到二分搜尋法的精隨,但要注意幾件事情:

  1. 要在N個元素中查找,N必須是有序的 (N1<N2<N3….. or N1>N2>N3)
  2. 要儲存在陣列之中且要連續存放

實現如下圖:

在13個數中尋找444這個數,代碼如下:

int binarySearch(int arr[],int target,int size){
int left,right,mid;
left = 0;
right = size-1;
while(left<=right){ 當left與right交錯時,代表根本沒這個數字
mid = (left+right)/2;
if(arr[mid]>target){ //中間數字比target大
right = mid-1;
}else if(arr[mid]<target){
left = mid+1;
}else{
return mid; //當arr[mid] == target時
}
}
return -1; //-1代表未找到
}
int main(){
int arr[13] = {5,16,39,45,51,98,100,202,226,321,368,444,501};
int result = binarySearch(arr,444,13);
printf("%d",result); //11
return 0;
}

二分查找O(logN)的速度應該是目前最快的算法了,上面但是這查找有很多限制,因此未來會教各種排序方法,以利二分查找的進行。中間剖一半的概念未來也會出現在"樹"這個資料結構上,因此非常重要。