Newsletter sign-up
View all newsletters

Enterprise Java Newsletter
Stay up to date on the latest tutorials and Java community news posted on JavaWorld

Sponsored Links

Optimize with a SATA RAID Storage Solution
Range of capacities as low as $1250 per TB. Ideal if you currently rely on servers/disks/JBODs

JavaWorld.com

Datastructures and algorithms, Part 1

Explore datastructures, algorithms, flowcharts, pseudocode, and arrays

By Jeff Friesen, JavaWorld.com, 05/02/03

  • Print
  • Feedback
.

Page 5 of 7

DECLARE INTEGER i, srch = 72
DECLARE INTEGER x [] = [ 20, 15, 12, 30, -5, 72, 456 ]
FOR i = 0 TO LENGTH (x) - 1
    IF x [i] IS srch THEN
       PRINT "Found ", srch
       END
    END IF
NEXT i
PRINT "Did not find ", srch
END


Listing 1 presents the Java equivalent to the pseudocode above:

Listing 1. LSearchDemo.java

// LSearchDemo.java
class LSearchDemo
{
   public static void main (String [] args)
   {
      int i, srch = 72;
      int [] x = { 20, 15, 12, 30, -5, 72, 456 };
      for (i = 0; i <= x.length - 1; i++)
           if (x [i] == srch)
           {
               System.out.println ("Found " + srch);
               return;
           }
      System.out.println ("Did not find " + srch);
   }
}


LSearchDemo produces the following output: 

Found 72


Linear-search's two advantages are simplicity and the ability to search either sorted or unsorted one-dimensional arrays. Its sole disadvantage is the time spent examining elements. The average number of elements to examine is half the one-dimensional array's length, and the maximum number of elements to examine is the entire length. For example, a one-dimensional array with 20 million elements requires linear-search to examine an average of 10 million elements and a maximum of 20 million elements. Because this examination time might seriously affect performance, use linear-search for one-dimensional arrays with relatively short lengths.

As with linear-search, the binary-search algorithm searches a one-dimensional array for a specific data item. Unlike linear-search, however, binary-search divides the one-dimensional array into lower and upper sections by calculating the middle element's index. If the data item is found in that element, binary-search ends. If the data item is numerically less than the data item in the middle element, binary-search calculates the index of the middle element in the lower section, ignores the upper section, and repeats. Otherwise, binary-search calculates the index of the middle element in the upper section, ignores the lower section, and repeats. The search continues until either the data item is found or the current section's lower bound exceeds the upper bound (which indicates that the data item is missing). The following pseudocode demonstrates this algorithm:

  • Print
  • Feedback

Resources