Skip to content

Instantly share code, notes, and snippets.

@daif
Created May 2, 2020 01:54
Show Gist options
  • Save daif/ab0f3ce14ebf586c5b1c5a633a525243 to your computer and use it in GitHub Desktop.
Save daif/ab0f3ce14ebf586c5b1c5a633a525243 to your computer and use it in GitHub Desktop.
Implementation of binary search in PHP
<?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;
}
?>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment