Binary Search in TypeScript

Nitin Bhardwaj
12y
6.1k
0
0

Article

Searching

Searching is the process of attempting to find a particular object in a collection. There are two possibile results of searching. First, the object exists in the collection and second, the object does not exist in the collection. We can search anywhere, as in any file, any page, any webpage etc. There are two types of searching:

Linear Search
Binary Search

Binary Search
A Binary Search is a way to search. It is difficult to compare to a linear search, and it's faster than a linear search. A Binary Search is also called a Half-Interval Search. It works on the Break & Search Concept.
In a Binary Search, the Key element is matched to the middle element of an array, if it matches then the value and index is returned; on other hand, if the Key element is less than the middle element of the array then it searches again in the left portion of the array and if the Key element is greater then it searches in the right portion of the array.

Example

The following example describes how to use a Binary Search in TypeScript. The following code implements a Binary Search which is used to determine whether a given element is present in an array and if it is present then at what location it occurs. It is very simple and works as follows.

Step 1

Open Visual Studio 2012 and click on "File" menu -> "New" -> "Project". A window is opened. Provide the name of your application, like "Binary_Search", then click on the Ok button.

Step 2

After Step 1 your project has been created. Solution Explorer, which is at the right side of Visual Studio, contains the js file, ts file, css file and html files.

Step 3

Binary_Search.ts

class Binary_Search

{

search()

{

var c, first, last, middle, n, search;

var x;

var array: number[] = [30];

n = parseInt(prompt("Enter how many elements you want: \n"));

for (c = 0; c < n;c++)

array[c]=parseInt(prompt("Enter "+n+" integers"));

for (x = 0; x < n; x++)

{

var span = document.createElement("span");

span.style.color = "Green";

span.innerText = "Enter "+ x +" Element -> " + array[x]+ "\n";

document.body.appendChild(span);

}

search = parseInt(prompt("Enter value to search\n"));

first = n;

last = 1;

{

middle = Math.floor((last + first) /2);

if (search < array[middle])

first = middle - 1;

elseif (search > array[middle])

last = middle+ 1;

}

while (search != array[middle] && last <= first)

if (search == array[middle])

{

var x = middle + 1;

var span = document.createElement("span");

span.style.color = "Blue";

span.innerText ="\nBinary search successfull!!\n"+ search+" Found in at Position: "+x+"\n";

document.body.appendChild(span);

}

else

{

alert("\n Search failed" +search+" not found\n"+search);

}

window.onload = () =>

{

var greeter = new Binary_Search();

greeter.search();

};

BinarySearch.html

<!DOCTYPEhtml>

<htmllang="en"xmlns="http://www.w3.org/1999/xhtml">

<head>

<metacharset="utf-8"/>

<title>Binary Search</title>

<linkrel="stylesheet"href="app.css"type="text/css"/>

<scriptsrc="app.js"></script>

</head>

<body>

<h2>Binary Search in TypeScript</h2>

<divid="content"/>

</body>

</html>

app.js

var Binary_Search = (function () {

function Binary_Search() { }

Binary_Search.prototype.search = function () {

var c;

var first;

var last;

var middle;

var n;

var search;

var x;

var array = [

];

n = parseInt(prompt("Enter how many elements you want: \n"));

for(c = 0; c < n; c++) {

array[c] = parseInt(prompt("Enter " + n + " integers"));

}

for(x = 0; x < n; x++) {

var span = document.createElement("span");

span.style.color = "Green";

span.innerText = "Enter " + x + " Element -> " + array[x] + "\n";

document.body.appendChild(span);

}

search = parseInt(prompt("Enter value to search\n"));

first = n;

last = 1;

do {

middle = Math.floor((last + first) / 2);

if(search < array[middle]) {

first = middle - 1;

} else {

if(search > array[middle]) {

last = middle + 1;

}

}while(search != array[middle] && last <= first)

{

}

if(search == array[middle]) {

var x = middle + 1;

var span = document.createElement("span");

span.style.color = "Blue";

span.innerText = "\nBinary search successfull!!\n" + search + " Found in at Position: " + x + "\n";

document.body.appendChild(span);

} else {

alert("\n Search failed" + search + " not found\n" + search);

}

};

return Binary_Search;

})();

window.onload = function () {

var greeter = new Binary_Search();

greeter.search();

};

Output 1

Enter how many elements in the array you want and then click on ok:

Output 2

Enter the elements in ascending order:

Output 3

Then enter a value to be searched for:

Output 4

If the specified number is present in the array then at what location does it occur?

Output 5

And if the specified number does not exist in the array then:

Up Next

Ebook Download

View all

Test

Read by 16 people

Download Now!

Learn

View all