Source: BinarySearch.phps - download

---

<?php
/* 
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 * 
 * BinarySearch.phps 0.1
 * Implementation of binary search in PHP
 * by Daif Alazmi (http://daif.net)
 * daif@daif.net
 * 
 * Link:
 *  http://daif.net/script/BinarySearch.phps
 *
 * Example:
 * $keyword = 'hello';
 * if(BinarySearch($keyword)) {
 *     echo true;
 * } else {
 *     echo false;
 * }
 *
 * Note:
 * Download top password list file and sort the file as following, 
 * wget https://github.com/danielmiessler/SecLists/raw/master/Passwords/Common-Credentials/10-million-password-list-top-1000000.txt
 * sort 10-million-password-list-top-1000000.txt -o 10-million-password-list-top-1000000.txt
*/


$time_usage = microtime(true);
$keyword    = 'hello';
if(BinarySearch($keyword))
{
    echo "Keyword: '$keyword' is found\n";
}
else
{
    echo "Keyword: '$keyword' is not found\n";
}
echo 'Time   : '. number_format((microtime(true) - $time_usage), 5, '.', '')." sec\n";


function BinarySearch($element='')
{
    $file   = '10-million-password-list-top-1000000.txt';
    $fp     = fopen($file, 'r');
    $max    = filesize($file);
    $min    = 0;
    $mid    = 0;
    while ($min <= $max)
    {
        // jump to the middle of $min and $max
        $mid    = floor(($min+$max) /2);
        // seek back to beginning of line.
        $i      = 0;
        do{
            $i++;
            fseek($fp, $mid-$i);
            $char = fgetc($fp);
        } while ($char != "\n" && $char !== false && $mid-$i >=0);
        // read the word from beginning of line to end of line.
        $word = trim(fgets($fp));
        // case-insensitive string comparison
        $comparison = strcasecmp($element, $word);
        // if $element is equal to $word return True
        if($comparison == 0)
        {
            return true;
        }
        // if the element is greater than the current word jump to the middle of next part. 
        elseif($comparison >= 1)
        {
            $min = ftell($fp)+1;
        }
        // else jump to the middle of previous part.
        else
        {
            $max = ftell($fp)-strlen($word)-1;
        }
    }
    return false;
}
?>