Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- <html xmlns = "http://www.w3.org/1999/xhtml">
- <head>
- <title>Binary Search</title>
- <script type = "text/javascript">
- <!--
- var a = new Array( 15 );
- for ( var i = 0; i < a.length; ++i )
- a[ i ] = 2 * i;
- // function called when "Search" button is pressed
- function buttonPressed()
- {
- var searchKey = searchForm.inputVal.value;
- searchForm.result.value =
- "Portions of array searched\n";
- // Array a is passed to binarySearch even though it
- // is a global variable. This is done because
- // normally an array is passed to a method
- // for searching.
- var element =
- binarySearch( a, parseInt( searchKey ) );
- if ( element != -1 )
- searchForm.result.value +=
- "\nFound value in element " + element;
- else
- searchForm.result.value += "\nValue not found";
- }
- // Binary search
- function binarySearch( theArray, key )
- {
- var low = 0; // low subscript
- var high = theArray.length - 1; // high subscript
- var middle; // middle subscript
- while ( low <= high ) {
- middle = ( low + high ) / 2;
- // The following line is used to display the
- // part of theArray currently being manipulated
- // during each iteration of the binary
- // search loop.
- buildOutput( theArray, low, middle, high );
- if ( key == theArray[ middle ] ) // match
- return middle;
- else if ( key < theArray[ middle ] )
- high = middle - 1; // search low end of array
- else
- low = middle + 1; // search high end of array
- }
- return -1; // searchKey not found
- }
- // Build one row of output showing the current
- // part of the array being processed.
- function buildOutput( theArray, low, mid, high )
- {
- for ( var i = 0; i < theArray.length; i++ ) {
- if ( i < low || i > high )
- searchForm.result.value += " ";
- // mark middle element in output
- else if ( i == mid )
- searchForm.result.value += a[ i ] +
- ( theArray[ i ] < 10 ? "* " : "* " );
- else
- searchForm.result.value += a[ i ] +
- ( theArray[ i ] < 10 ? " " : " " );
- }
- searchForm.result.value += "\n";
- }
- // -->
- </script>
- </head>
- <body>
- <form name = "searchForm" action = "">
- <p>Enter integer search key<br />
- <input name = "inputVal" type = "text" />
- <input name = "search" type = "button" value =
- "Search" onclick = "buttonPressed()" /><br /></p>
- <p>Result<br />
- <textarea name = "result" rows = "7" cols = "60">
- </textarea></p>
- </form>
- </body>
- </html>
Advertisement
Add Comment
Please, Sign In to add comment