二分探索（binarySearch）を10種類の言語で書いてみた

何故書くか？は前前前回書いたので、以下、即本題。

実行環境は今までと同じく、coding groundを使用。

本当は定義したメソッドだけ書いておきたいのだけど、後々動作確認したいと思った時にコピペで済むので前処理等も書いておいた。

JavaScript

function binarySearch(arr, target) {
    let head = 0,
        mid,
        tail = arr.length;

    while(head <= tail){
        mid = Math.floor((head + tail) / 2);
        if (arr[mid] === target) {
            return mid;
        } else if(arr[mid] < target) {
            head = mid + 1;
        } else {
            tail = mid -1;
        }
    }
    return -1;
}
console.log(binarySearch([104, 150, 165, 304, 354, 413, 541, 865], 304));

PHP

function binarySearch($arr, $target) {
    $head = 0;
    $tail = count($arr) - 1 ;
    while ($head <= $tail) {
        $mid = floor(($head + $tail) / 2);
        if ($arr[$mid] === $target) {
            return $mid;
        } else if ($arr[$mid] < $target) {
            $head = $mid + 1;
        } else {
            $tail = $mid -1;
        }
    }
    return -1;
}

echo (binarySearch([104, 150, 165, 304, 354, 413, 541, 865], 304));

Perl

use POSIX qw(floor);

my @arr = (104, 150, 165, 304, 354, 413, 541, 865);
my $result = &binarySearch(\@arr, 304);
print $result;
sub binarySearch {
    my ($arr, $target) = @_;
    my $head = 0;
    my $mid;
    my $tail = $#arr;

    while ($head <= $tail) {
        $mid = floor(($head + $tail) / 2);
        if ($arr[$mid] == $target) {
            return $mid;
        } elsif ($arr[$mid] < $target) {
            $head = $mid + 1;
        } else {
            $tail = $mid - 1;
        }
    }
    return -1;
}

Python

import math
def binarySearch(arr, target):
    head = 0
    tail = len(arr) - 1
    while head <= tail:
        mid = math.floor((head + tail) / 2)
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            head = mid + 1
        else:
            tail = mid - 1
    return False

print(binarySearch([104, 150, 165, 304, 354, 413, 541, 865], 304))

Ruby

def binarySearch(arr, target)
    head = 0
    tail = arr.size - 1
    while head <= tail do
        mid = ((head + tail) / 2).floor
        if arr[mid] == target
            return mid
        elsif arr[mid] < target
            head = mid + 1;
        else
            tail = mid -1;
        end
    end
    return -1
end

print binarySearch([104, 150, 165, 304, 354, 413, 541, 865], 304)

Go

package main

import (
    "fmt"
    "math"
)

func main() {
fmt.Println(binarySearch([]int{104, 150, 165, 304, 354, 413, 541, 865}, 304));
}

func binarySearch(arr []int, target int) int {
    head := 0;
    tail := len(arr) - 1;
    for head <= tail {
        mid := int(math.Floor(float64(head + tail) / 2));
        if arr[mid] == target {
            return mid;
        } else if arr[mid] < target {
            head = mid + 1;
        } else {
            tail = mid - 1;
        }
    }
    return -1;
}

Kotlin

func binarySearch(arr: [Int], target: Int) -> Int {
    var head = 0
    var mid = 0
    var tail = arr.count - 1;
    while head <= tail {
        mid = Int(floor(Double(head + tail) / 2))
        if arr[mid] == target {
            return mid;
        } else if arr[mid] < target {
            head = mid + 1;
        } else {
            tail = mid - 1;
        }
    }
    return -1;
}

print(binarySearch(arr: [104, 150, 165, 304, 354, 413, 541, 865], target: 304))

Swift

fun main(args: Array<String>) {
    println(binarySearch(arrayOf(104, 150, 165, 304, 354, 413, 541, 865), 304));
}

fun binarySearch(arr: Array<Int>, target: Int): Int {
    var head = 0
    var tail = arr.size-1
    while (head <= tail) {
        var mid = Math.floor((head + tail).toDouble() / 2).toInt()
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            head = mid + 1;
        } else {
            tail = mid - 1;
        }
    }
    return -1;
}

C

using System.IO;
using System;

class Program
{
    static void Main()
    {
        int[] arr = { 104, 150, 165, 304, 354, 413, 541, 865 };
        Console.WriteLine(binarySearch(arr, 304));
    }

    static int binarySearch(int[] arr, int target) {
        int head = 0;
        int tail = arr.Length - 1;
        while (head <= tail) {
            int mid = (int)Math.Floor((double)(head + tail) / 2);
            if (arr[mid] == target) {
                return mid;
            } else if(arr[mid] < target) {
                head = mid + 1;
            } else {
                tail = mid - 1;
            }
        }
        return -1;
    }
}

C

#include <stdio.h>
#include <math.h>

int binarySearch(int arr[], int len, int target) {
    int head = 0;
    int tail = len - 1;
    while (head <= tail) {
        double tmp = (head + tail) / 2;
        int mid = (int) floor(tmp);
        if(arr[mid] == target) {
            return mid;    
        } else if(arr[mid] < target) {
            head = mid + 1;
        } else {
            tail = mid - 1;
        }
    }
    return -1;
}

int main() {
    int arr[] = {104, 150, 165, 304, 354, 413, 541, 865};
    printf("%d", binarySearch(arr, 8, 304));

    return 0;
}