Binary Search in Perl

最近在學Perl...
外加大學資結都在鬼混所以去旁聽大學部的資檔結...

今天老師講到Binary Search
所以就用Perl自己來寫一個
然後就遇到了天大的小問題......

Perl算是動態語言所以變數都不需要型態宣告
且Perl一律使用「倍精度浮點數」，因此沒有整數值這東西
然後剛才在實作Binary Search的時候完全忽略這點的後果就是想不通Bug的原因

問題如下：
定義了一個串列為 3 7 14 20 23 32 41 44 56 57 73 89 93
然後開始用新學的語法開始劈哩啪啦的把Binary Search寫出來
很開心的要來測試一下，而且心裡想說怎麼可能會有Bug......
沒想到測到 7 這個數就發現竟然找不到它......
繼續測下去竟然有更多找不到的值，包括 20 56...
以為是演算法寫錯了，可是怎麼看都沒問題
最後把所有與演算法相關的變數($begin $end $mid)都印出來
才發現小數點的問題......

問題解決：

target	begin	end	mid
7	0	12	6
	0	5	2(2.5)
	0	1(1.5)	0(0.75)
	1(1.75)	1(1.5)	1(?)
20	0	12	6
	0	5	2(2.5)
	3(3.5)	5	4(4.25)
	3(3.5)	3(3.25)	3(?)
56	0	12	6
	7	12	9(9.5)
	7	8(8.5)	7(7.75)
	8(8.75)	8(8.5)	8(?)

從上面的表格可以看到幾個發生問題的值的搜尋過程

圓括號內的值是沒有把浮點數轉為整數的實際值

可以看出最後應該要找到結果的那邊begin都大於end

難怪while迴圈都會在此終止......

最後解法就是將 ($begin+$end)/2 以 int來轉型 → int (($begin+$end)/2)

以下程式碼：

use 5.012;

my @datas = qw( 3 7 14 20 23 32 41 44 56 57 73 89 93 );
my $locn =  &binary_search(56, @datas);
say $locn;

sub binary_search{
 my ($target, @list) = @_;
 my ($begin, $end, $mid) = (0, $#list, 0);

 while($begin <= $end){
  $mid = int(($begin + $end) / 2); #就是這行卡了我老半天...
  if($target > $list[$mid]){
   $begin = $mid + 1;
  }else{
   if($target < $list[$mid]){
    $end = $mid - 1;
   }else{
    return int($mid);
   }
  }
 }
 return -1;
}