RokiAdhytama

Binary Search - Chapter 10

Jul 3rd, 2022
1,003
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. <html xmlns = "http://www.w3.org/1999/xhtml">
  2.    <head>
  3.       <title>Binary Search</title>
  4.  
  5.       <script type = "text/javascript">
  6.          <!--
  7.          var a = new Array( 15 );
  8.  
  9.          for ( var i = 0; i < a.length; ++i )
  10.             a[ i ] = 2 * i;
  11.  
  12.          // function called when "Search" button is pressed
  13.          function buttonPressed()
  14.          {
  15.             var searchKey = searchForm.inputVal.value;
  16.      
  17.             searchForm.result.value =
  18.                "Portions of array searched\n";
  19.  
  20.             // Array a is passed to binarySearch even though it
  21.             // is a global variable. This is done because
  22.             // normally an array is passed to a method
  23.             // for searching.
  24.             var element =
  25.                    binarySearch( a, parseInt( searchKey ) );
  26.  
  27.             if ( element != -1 )
  28.                searchForm.result.value +=
  29.                   "\nFound value in element " + element;
  30.             else
  31.                searchForm.result.value += "\nValue not found";
  32.          }
  33.    
  34.          // Binary search
  35.          function binarySearch( theArray, key )
  36.          {
  37.             var low = 0;                    // low subscript
  38.             var high = theArray.length - 1; // high subscript
  39.             var middle;                     // middle subscript
  40.  
  41.             while ( low <= high ) {
  42.                middle = ( low + high ) / 2;
  43.  
  44.                // The following line is used to display the
  45.                // part of theArray currently being manipulated
  46.                // during each iteration of the binary
  47.                // search loop.
  48.                buildOutput( theArray, low, middle, high );
  49.  
  50.                if ( key == theArray[ middle ] )  // match
  51.                   return middle;
  52.                else if ( key < theArray[ middle ] )
  53.                   high = middle - 1; // search low end of array
  54.                else
  55.                   low = middle + 1; // search high end of array
  56.             }
  57.  
  58.             return -1;   // searchKey not found
  59.          }
  60.  
  61.          // Build one row of output showing the current
  62.          // part of the array being processed.
  63.          function buildOutput( theArray, low, mid, high )
  64.          {
  65.             for ( var i = 0; i < theArray.length; i++ ) {
  66.                if ( i < low || i > high )
  67.                   searchForm.result.value += "    ";
  68.                // mark middle element in output
  69.                else if ( i == mid )
  70.                   searchForm.result.value += a[ i ] +
  71.                      ( theArray[ i ] < 10 ? "*  " : "* " );
  72.                else                                          
  73.                   searchForm.result.value += a[ i ] +
  74.                      ( theArray[ i ] < 10 ? "   " : "  " );
  75.             }
  76.  
  77.             searchForm.result.value += "\n";
  78.          }
  79.          // -->
  80.       </script>
  81.    </head>
  82.  
  83.    <body>
  84.       <form name = "searchForm" action = "">
  85.          <p>Enter integer search key<br />
  86.          <input name = "inputVal" type = "text" />
  87.          <input name = "search" type = "button" value =
  88.             "Search" onclick = "buttonPressed()" /><br /></p>
  89.          <p>Result<br />
  90.          <textarea name = "result" rows = "7" cols = "60">
  91.          </textarea></p>
  92.       </form>
  93.    </body>
  94. </html>
Advertisement
Add Comment
Please, Sign In to add comment