Home | | Internet & World Wide Web HOW TO PROGRAM | | Internet Programming | | Web Programming | Searching Arrays: Linear Search and Binary Search - JavaScript(JS)

Chapter: Internet & World Wide Web HOW TO PROGRAM - The Ajax Client - JavaScript: Arrays

| Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail |

Searching Arrays: Linear Search and Binary Search - JavaScript(JS)

Often, a programmer will be working with large amounts of data stored in arrays.

Searching Arrays: Linear Search and Binary Search

 

Often, a programmer will be working with large amounts of data stored in arrays. It may be necessary to determine whether an array contains a value that matches a certain key value. The process of locating a particular element value in an array is called searching. In this section we discuss two searching techniques—the simple linear search technique (Fig. 10.10) and the more efficient binary search technique (Fig. 10.11).

 

Searching an Array with Linear Search

 

The script in Fig. 10.10 performs a linear search on an array. Function linearSearch (de-fined in lines 42–50) uses a for statement containing an if statement to compare each element of an array with a search key (lines 45–47). If the search key is found, the function returns the subscript value (line 47) of the element to indicate the exact position of the search key in the array. [Note: The loop (lines 45–47) in the linearSearch function ter-minates, and the function returns control to the caller as soon as the return statement in its body executes.] If the search key is not found, the function returns a value of –1. The function returns the value –1 because it is not a valid subscript number.

 

      <?xml version = "1.0" encoding = "utf-8"?>

 

      <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"

 

      "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">

 

      <!-- Fig. 10.10: LinearSearch.html -->

 

      <!-- Linear search of an array. -->

 

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

 

      <head>

 

      <title>Linear Search of an Array</title>

 

        <script type = "text/javascript">

        <!--

 

        var a = new Array( 100 );  // create an Array

 

// fill Array with even integer values from 0 to 198

            for ( var i = 0; i < a.length; ++i )

            a[ i ] = 2 * i;

        // function called when "Search" button is pressed

 

        function buttonPressed()

{

// get the         input text field

var inputVal = document.getElementById( "inputVal" );

           

// get the         result text field

var result        = document.getElementById( "result" );

           

// get the         search key from the input text field

var searchKey = inputVal.value;

           

// Array a        is passed to linearSearch even though it

// is a global variable. Normally an array will

// be passed to a method for searching.

var element = linearSearch( a, parseInt( searchKey ) );           

           

if ( element != -1 )

result.value = "Found value in element " + element;

else

result.value = "Value not found";

} // end function buttonPressed

        // Search "theArray" for the specified "key" value

 

        function linearSearch( theArray, key )

{

// iterates through each element of the array in order

            for (     var n = 0; n < theArray.length; ++n )        

            if          ( theArray[ n ] == key )        

                        return n;        

        return -1;

 

        } // end function linearSearch

        // -->

 

        </script>

 

        </head>

        <body>

 

        <form action  = "">

 

        <p>Enter integer search key<br />

 

        <input id = "inputVal" type = "text" />

 

        <input type = "button" value = "Search" onclick = "buttonPressed()" /><br /></p>

 

        <p>Result<br />

 

        <input id = "result" type = "text" size = "30" /></p>

 

        </form>

 

        </body>

 

</html>


Fig. 10.10 | Linear search of an array.

If the array being searched is not in any particular order, the value is just as likely to be found in the first element as the last. On average, therefore, the program will have to compare the search key with half the elements of the array.

 

The program contains a 100-element array (defined in line 12) filled with the even integers from 0 to 198. The user types the search key in a text field (defined in the XHTML form in lines 56–63) and clicks the Search button to start the search. [Note: The array is passed to linearSearch even though the array is a global script variable. We do this because arrays are normally passed to functions for searching.]

 

Searching an Array with Binary Search

 

The linear search method works well for small arrays or for unsorted arrays. However, for large arrays, linear searching is inefficient. The binary search algorithm is more efficient, but it requires that the array be sorted. The first iteration of this algorithm tests the middle element in the array. If this matches the search key, the algorithm ends. Assuming the array is sorted in ascending order, then if the search key is less than the middle element, it cannot match any element in the second half of the array and the algorithm continues with only the first half of the array (i.e., the first element up to, but not including, the middle ele-ment). If the search key is greater than the middle element, it cannot match any element in the first half of the array and the algorithm continues with only the second half of the array (i.e., the element after the middle element through the last element). Each iteration tests the middle value of the remaining portion of the array. If the search key does not match the element, the algorithm eliminates half of the remaining elements. The algo-rithm ends by either finding an element that matches the search key or reducing the sub-array to zero size.

As an example consider the sorted 15-element array

 

2 3  5  10 27 30 34 51 56 65 77 81 82 93 99

 

and a search key of 65. A program implementing the binary search algorithm would first check whether 51 is the search key (because 51 is the middle element of the array). The search key (65) is larger than 51, so 51 is discarded along with the first half of the array (all elements smaller than 51.) Next, the algorithm checks whether 81 (the middle element of the remainder of the array) matches the search key. The search key (65) is smaller than 81, so 81 is discarded along with the elements larger than 81. After just two tests, the algo-rithm has narrowed the number of values to check to three (56, 65 and 77). The algorithm then checks 65 (which indeed matches the search key), and returns the index of the array element containing 65. This algorithm required just three comparisons to determine whether the search key matched an element of the array. Using a linear search algorithm would have required 10 comparisons. [Note: In this example, we have chosen to use an ar-ray with 15 elements so that there will always be an obvious middle element in the array. With an even number of elements, the middle of the array lies between two elements. We implement the algorithm to choose the lower of those two elements.]

 

Figure 10.11 presents the iterative version of function binarySearch (lines 40–64). Function binarySearch is called from line 31 of function buttonPressed (lines 18–37)— the event handler for the Search button in the XHTML form. Function binarySearch receives two arguments—an array called theArray (the array to search) and key (the search key). The array is passed to binarySearch even though the array is a global variable. Once again, we do this because an array is normally passed to a function for searching. If key matches the middle element of a subarray (line 55), middle (the subscript of the current element) is returned, to indicate that the value was found and the search is complete. If key does not match the middle element of a subarray, the low subscript or the high sub-script (both declared in the function) is adjusted, so that a smaller subarray can be searched. If key is less than the middle element (line 57), the high subscript is set to middle - 1 and the search is continued on the elements from low to middle - 1. If key is greater than the middle element (line 59), the low subscript is set to middle + 1 and the search is continued on the elements from middle + 1 to high. These comparisons are per-formed by the nested ifelse statement in lines 55–60.

 

 

 

      <?xml version = "1.0" encoding = "utf-8"?>

 

      <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"

 

      "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">

 

      <!-- Fig. 10.11: BinarySearch.html -->

 

      <!-- Binary search of an array. -->

 

      <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 inputVal = document.getElementById( "inputVal" );

var result = document.getElementById( "result" );

var searchKey = inputVal.value;

           

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 )

            result.value += "\nFound value in element " + element;

else

            result.value += "\nValue not found";

} // end function buttonPressed

        // binary search function

 

        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

} // end while

        return -1;   // searchKey not found

 

        } // end function binarySearch

        // Build one row of output showing the current

 

        // part of the array being processed.

 

        function buildOutput( theArray, low, mid, high )

{

var result = document.getElementById(   "result" );

                                                           

for (     var i = 0; i       < theArray.length;    i++ )

{                                                          

if          ( i < low ||       i > high )                   

            result.value   += "     ";                     

else if ( i == mid ) // mark middle element in output

            result.value   += theArray[ i ] +      

            ( theArray[ i ] < 10 ? "*          "           : "* " );

else                                        

            result.value   += theArray[ i ] +      

            ( theArray[ i ] < 10 ? "           "           : "  " );

} // end for                                         

        result.value += "\n";

 

        } // end function buildOutput

        // -->

 

        </script>

 

</head>

      <body>

 

      <form action = "">

 

      <p>Enter integer search key<br />

 

      <input id = "inputVal" type = "text" />

 

      <input type = "button" value = "Search"

      onclick = "buttonPressed()" /><br /></p>

 

      <p>Result<br />

 

      <textarea id = "result" rows = "7" cols = "60">

 

      </textarea></p>

 

      </form>

       </body>

 

</html>


Fig. 10.11 | Binary search of an array.

In a worst-case scenario, searching an array of 1023 elements will take only 10 com-parisons using a binary search. Repeatedly dividing 1024 by 2 (because after each comparison we are able to eliminate half of the array) yields the values 512, 256, 128, 64, 32, 16, 8, 4, 2 and 1. The number 1024 (210) is divided by 2 only ten times to get the value 1.

 

Dividing by 2 is equivalent to one comparison in the binary search algorithm. An array of about one million elements takes a maximum of 20 comparisons to find the key. An array of about one billion elements takes a maximum of 30 comparisons to find the key. When searching a sorted array, this is a tremendous increase in performance over the linear search that required comparing the search key to an average of half the elements in the array. For a one-billion-element array, this is the difference between an average of 500 million com-parisons and a maximum of 30 comparisons! The maximum number of comparisons needed for the binary search of any sorted array is the exponent of the first power of 2 greater than the number of elements in the array.

 

Our program uses a 15-element array (defined at line 12). The first power of 2 greater than the number of elements is 16 (24), so binarySearch requires at most four comparisons to find the key. To illustrate this, line 53 calls method buildOutput (declared in lines 68–85) to output each subarray during the binary search process. Method buildOutput marks the middle element in each subarray with an asterisk (*) to indicate the element with which the key is compared. No matter what search key is entered, each search in this example results in a maximum of four lines of output—one per comparison.


Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail


Copyright © 2018-2020 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.