1-PHP Binary Search Array is used to search the given value in the array.
2-In php there is no function for the binary search like java or other language.
Binary search algorithm in PHP
Binary search is a search algorithm that is dramatically faster than PHP’s internal functions (such as array_search) when searching ordered data.
Demo link :
Code link :
Demo code run :
Binary search implementation :
1-first create array,
2-check middle value in array,
3-search value and middle value is equal then search value found,
4-if search value is less than middle calculated value then again search left side if search value should be found or not,
4-if search value is greater than middle calulcated value search right side now,
The binary search is perhaps the most famous and best suitable search algorithm for sorted arrays. Indeed when the array is sorted it is useless to check every single item against the desired value.
Here’s a sample implementation of this algorithm on PHP. Obviously the nature of this approach is guiding us to a recursive implementation,
How does it work?
PHP’s internal function array_search is an example of a linear search; it will iterate over the entire data set until it finds a match working from front to back.
A binary search tree is a rooted binary tree, whose internal nodes each store a key (and optionally, an associated value) and each have two distinguished sub-trees, commonly denoted left and right. The tree additionally satisfies the binary search tree property, which states that the key in each node must be greater than or equal to any key stored in the left sub-tree, and less than or equal to any key stored in the right sub-tree.(The leaves (final nodes) of the tree contain no key and have no structure to distinguish them from one another. Leaves are commonly represented by a special leaf or nil symbol, a NULL pointer, etc.)
Generally, the information represented by each node is a record rather than a single data element. However, for sequencing purposes, nodes are compared according to their keys rather than any part of their associated records.
The major advantage of binary search trees over other data structures is that the related sorting algorithms and search algorithms such as in-order traversal can be very efficient; they are also easy to code.
Binary search trees are a fundamental data structure used to construct more abstract data structures such as sets, multisets, and associative arrays. Some of their disadvantages are as follows:
The shape of the binary search tree depends entirely on the order of insertions and deletions, and can become degenerate.
When inserting or searching for an element in a binary search tree, the key of each visited node has to be compared with the key of the element to be inserted or found.
The keys in the binary search tree may be long and the run time may increase.
After a long intermixed sequence of random insertion and deletion, the expected height of the tree approaches square root of the number of keys, which grows much faster than log n
Following image diagram shows binary search algorithm,binary search is very simple search one by one array record.it is very fast to search algorithm.
Following example shows binary search method in php
Please create following file structure :
1-action.php,
2-index.php,
3-error.php,
4-binary.js,
5-jquery.validate.js,
1-index.php file
Contains search value ,start value and end value. In index.php file include in header section bootstrap link as well as js include
Code :
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<title>Jquery validation</title>
<link href="https://maxcdn.bootstrapcdn.com/bootstrap/3.3.5/css/bootstrap.min.css" rel="stylesheet">
<link href="error.css" rel="stylesheet">
<script src="https://code.jquery.com/jquery-3.1.1.js" integrity="sha256-16cdPddA6VdVInumRGo6IbivbERE8p7CQR3HzTBuELA=" crossorigin="anonymous">
</script>
<script src="https://maxcdn.bootstrapcdn.com/bootstrap/3.3.5/js/bootstrap.min.js"></script>
<script src="jquery.validate.js"></script>
<script src="binary.js.js"></script>
</head>
<body>
<!-- start:header -->
<nav class="navbar navbar-default navbar-fixed-top">
<div class="container-fluid">
<!-- Brand and toggle get grouped for better mobile display -->
<div class="navbar-header">
<a class="navbar-brand" href="#">Free Teachnology</a>
</div>
<!-- Collect the nav links, forms, and other content for toggling -->
<div class="collapse navbar-collapse" id="bs-example-navbar-collapse-1">
<ul class="nav navbar-nav">
<li class="active"><a href="#">Home <span class="sr-only"></span></a></li>
<li><a href="#">About us</a></li>
<li><a href="#">Contact us</a></li>
</ul>
</div><!-- /.navbar-collapse -->
</div><!-- /.container-fluid -->
</nav>
<!-- end:header -->
<br><br><br>
<div class="cleafix"></div>
<div class="container">
<div class="alert alert-info">
<strong>Hi..</strong> PHP binary search.
</div>
<div class="alert alert-warning">
<a href="https://drive.google.com/open?id=0BxmTZPVcu72fd1dnTFRpS2w2Uk0" class="btn btn-xs btn-warning pull-right" target="blank();">Click</a>
<strong> Code download link-</strong>
</div>
<br><br>
</div>
<div class="container text-center card">
<h3>Binary search Program</h3>
<div class="col-md-4">
<form action="action.php" method="post" id="signupFrom" name="signupFrom" accept-charset="utf-8">
<label for="name ">Search Value</label>
<input type="text" name="search" id="search" class="form-control" placeholder="Search" />
<div class="clearfix"></div>
<label for="name">Start value</label>
<input type="text" name="startvalue" id="startvalue" class="form-control" placeholder="Enter start value" />
<div class="clearfix"></div>
<label for="contact">End value</label>
<input type="text" name="endvalue" id="endvalue" class="form-control" placeholder="Enter end value" />
<div class="clearfix"></div>
</br>
<button type="submit" name="submit" id="submit" class="btn btn-primary">Search Now</button>
</form>
</div>
<div class="col-md-4" id="shows" style="display:none;">
Postion : <div id="postion"> </div>
Found Value : <div id="found"></div>
</div>
</div>
<link href="//maxcdn.bootstrapcdn.com/font-awesome/4.2.0/css/font-awesome.min.css" rel="stylesheet">
</br>
<!-- Start::footer -->
<footer>
<div class="footer footer-bottom">
<div class="container">
<p class="pull-left"> Copyright © <?php echo date('Y');?>. Design and Develop by - Disuza Jen. </p>
<div class="pull-right">
<ul class="nav nav-pills payments">
<li><i class="fa fa-facebook"></i></li>
<li><i class="fa fa-google"></i></li>
<li><i class="fa fa-twitter"></i></li>
<li><i class="fa fa-link"></i></li>
</ul>
</div>
</div>
</div>
<!--/.footer-bottom-->
</footer>
<!-- End::footer -->
<link rel="stylesheet" type="text/css" href="//maxcdn.bootstrapcdn.com/font-awesome/4.1.0/css/font-awesome.min.css">
<br>
<!--Start:: if success ajax call then show message -->
<div id="demo"></div>
<!--End:: if success ajax call then show message -->
</body>
</html>
Above file input text box is three
1-search text box,
2-start value text box,
3-end value text box.
2-action.php :
Action.php files show submit action result which is submit bye you.
Code :
<?php
/*
*Post value::-
*/
///post value::
$search=$_POST['search'];
$startvalue=$_POST['startvalue'];
$endvalue=$_POST['endvalue'];
$final_create_array=array();
for($i=$startvalue;$i<=$endvalue;$i++)
{
$final_create_array[]=$i;
}
$left=1;
$right=sizeof($final_create_array)-1;
$middle=sizeof(($left+$right)/2)-1;
$mid_val=$final_create_array[$middle];
BinarySearch($search,$final_create_array,$left, $right);
function BinarySearch($key, $list, $left, $right) {
//
if ($left > $right) {
$result=array('status'=>'2','message'=>'start value should be less than end value');
echo json_encode($result);
exit();
}
$mid = round(($left + $right)/2);
if ($list[$mid] == $key) {
$value= $list[$mid];
$position= $mid;
$result=array('status'=>1,'position'=>$position,'value'=>$value);
echo json_encode($result);
exit();
} elseif ($list[$mid] > $key) {
BinarySearch($key, $list, $left, $mid - 1);
} elseif ($list[$mid] < $key) {
BinarySearch($key, $list, $mid + 1, $right);
}
}?>
Above code is simple first store submit value in variable :
<?php///post value::
$search=$_POST['search']; $startvalue=$_POST['startvalue']; $endvalue=$_POST['endvalue']; ?>
Now submit value store in variable then start value and end value create array which is you want to search record or find record in array.
<?php $final_create_array=array();
for($i=$startvalue;$i<=$endvalue;$i++)
{
$final_create_array[]=$i;
}?>
After that return BinarySearch() function and this function include following code
Code :
<?php function BinarySearch($key, $list, $left, $right) {
//
if ($left > $right) {
$result=array('status'=>'2','message'=>'start value should be less than end value');
echo json_encode($result);
exit();
}
$mid = round(($left + $right)/2);
if ($list[$mid] == $key) {
$value= $list[$mid];
$position= $mid;
$result=array('status'=>1,'position'=>$position,'value'=>$value);
echo json_encode($result);
exit();
} elseif ($list[$mid] > $key) {
BinarySearch($key, $list, $left, $mid - 1);
} elseif ($list[$mid] < $key) {
BinarySearch($key, $list, $mid + 1, $right);
}
}?>
BinarySearch() function pass following parameter :
1-$search,
2-$final_create_array,
3-$left,
4-$right,
BinarySearch($search,$final_create_array,$left, $right);
Above example of binary search check first left value is not greater than right value,
Calculate mid value as :
$mid = round(($left + $right)/2);
Now created array check mid value and search value is equal or not if equal then show find value and find of position :
if ($list[$mid] == $key) {
$value= $list[$mid];
$position= $mid;
//json response return :-
$result=array('status'=>1,'position'=>$position,'value'=>$value);
echo json_encode($result);
exit();
}
If mid value is less than key value then mid value is decreased by 1 other wise mid value adding 1.
<?php
if ($list[$mid] > $key) {
BinarySearch($key, $list, $left, $mid - 1);
} elseif ($list[$mid] < $key) {
BinarySearch($key, $list, $mid + 1, $right);
}
?>
Binary.js :
In index.php files all text field submit value then binary.js file call and form submitHandler event call if validation is true.
On submitHandler ajax function call and show the response on home page :
Code :
< var startvalue = $.trim($('#startvalue').val());
var endvalue = $.trim($('#endvalue').val());
var search = $.trim($('#search').val());
$.ajax({
type: "POST",
url: "action.php",
async: true,
data: {search:search,startvalue:startvalue,endvalue:endvalue},
success: function(html) {
var result=$.parseJSON(html);
if(result.status==2) {
$("#shows").hide();
alert('Enter correct value.');
} else if(result.status==1) {
$("#shows").show();
$("#postion").html(result.position);
$("#found").html(result.value);
} else {
alert('Something goes wrong.');
}
}
});
>
First get value of textfield and pass to action.php page,ajax type is post and json encoded repose convert in array using parseJSON() function and show result as per response status type.
I hope that my blog binary search program you like and enjoy my code, if you like please share and comment on.
Thanks you.
Comments