Binary search in javascript

Posted By : Rajan Rawat | 16-Dec-2016

Binary Search Tree

Let's take an example of javascript array of 25 elements.

var array = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97];

Now in this array we want to know number 67 is present or not.

Now we will stat the binary search by finding the mid of the array and then if mid is greater than the searched element then we find the mid of the other part of the array.

For finding the mid we use the formula mid=(min+max)/2

In the above picture you see the 25 elements of array. Now you have to find the mid of this array using the formula mid=(min+max)/2

Now i think the mid will be 41 that is index 12. so if we compare the value 41 is less than 67. So now we will find the mid again.

In the above figure you can see we will find the mid in second part of the array because 41 is less than 67. But this time your the value of your min will be min+1.

In the above example you can see that our new mid is 67.

mid=(min+max)/2

that is mid=(13+24)/2 mid will be 18.5 so we take the round figure 18 and guess what we find our answer. It only took two guesses to find the right answer.

Now lets take an live example of binary search in javascript

<html>
<head>
<title>Binary Search program using javascript</title>
<script>
function binary()
{
var n=parseInt(prompt("Insert the array length:"));
var X= new array(n);
var p=0;
for (var i=0; i<X.length; i++)
{
X[i]=parseInt(prompt("Insert the elements of array"));
}
for(var i=0;i<X.length;i++)
{
for(var j=i+1;j<X.length;j++)
{
if(X[i]>X[j])
{
var t=X[i];
X[i]=X[j];
X[j]=t;
}
}
}
var k=parseInt(prompt("enter the element to find"));
var i=0;
var u=parseInt(X.length-1);
while(i<=u)
{
var m=parseInt((i+u)/2);
if(k==X[m])
{
p=1;
break;
}
else if(k>X[m])
{
i=m+1;
}
else if(k<X[m])
{
u=m-1;
}
}
if(p==1)
document.writeln("element found at :"+m);
else
document.writeln("element not found");

}
</script>
</head>
<body onLoad="binary();"></body>
</html>