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

二分查找法式大家最熟悉，的查找方式之一，運行效率也非常快，時間複雜度為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)的速度應該是目前最快的算法了，上面但是這查找有很多限制，因此未來會教各種排序方法，以利二分查找的進行。中間剖一半的概念未來也會出現在"樹"這個資料結構上，因此非常重要。