goとperlで二分探索(binray_search)

kindleストアで翔泳社の50%OFFキャンペーンやってたからこの本を買った。
今までアルゴリズムの勉強を避けてたのでちゃんと読んでみようと思う。

なっとく! アルゴリズム

なっとく! アルゴリズム

この本はサンプルコードがpython2.7で書かれてるので、勉強中のgoと、仕事で使ってるperlで書き直してみようと思う。

goで二分探索

package main

import(
  "fmt"
  "errors"
)

# list 検索対象の配列
# item 検索対象の数値
func binary_search(list []int, item int) (int, error) {
  low := 0
  high := len(list) - 1
  
  for low <= high {
    mid := (low + high) / 2
    guess := list[mid]
    
    if item == guess {
      return mid, nil
    } else if item < guess {
      high = mid - 1
    } else if item > guess {
      low = mid + 1
    }
  }
  
  return -1, errors.New("not found")
}

func main(){
    # 配列[1,2,3,4,5]から5の位置を検索
    result, err := binary_search([]int{1,2,3,4,5}, 5)
    if err != nil {
      log.Fatal(err)
    }
    fmt.Println(result)
}

itemが見つからなかったとき、とりあえず-1を返すようにしてるけどなんかイケてない気がする。 動的言語とかだったら単純にnilとか返せば良さそうだけど。

perlで二分探索

sub binary_search {
  my ($list, $item) = @_;
  my $low = 0;
  my $high = scalar @$list - 1;
  
  while ($low <= $high) {
    my $mid = int(($low + $high) / 2);
    $guess = $list->[$mid];
    if ($item == $guess) {
      return $mid;
    } elsif ($item < $guess) {
      $high = $mid - 1;
    } elsif ($item > $guess) {
      $low = $mid + 1;
    }
  }

  return undef;
}

my $result = binary_search([1, 2, 3, 4, 5], 3);
($result) ? print $result : print 'not found';