APCS Ch 6: Sorting and Searching Methods

Sequential Search

A sequential search is self-explanatory. It goes through each value on the array and returns whatever value you’re looking for. For sequential searches, the for each loop is really handy. For example, this piece of code (a method actually) from vogella demonstrates the search to see if there is a value b in the int array a:

public static boolean contains(int[] a, int b){
        for (int i : a) {
            if (i==b){
                return true;
  }
 }
           return false;
}

You would use a sequential search when the elements in the array aren’t sorted.

Binary Search

If I told you to guess a number I’m thinking of between 0 and 100 and I would tell you whether your guess was too high or too low after each guess, what would be the first number you’d guess? 50, right? If I said too high, then you’d guess 25; if too low, you’d guess 75. What a binary search does is divide the range of possible values in half. This makes the binary search more efficient than the sequential search when the array is sorted.

Here’s another method from vogella that demonstrates the use of binary search to see if the number b is contained within a sorted int array a:

public static boolean contains(int[] a, int b) {
        if (a.length == 0) {
            return false;
        }
        int low = 0;
        int high = a.length-1;

        while(low <= high ) {
            int middle = (low+high) /2;
            if (b> a[middle] ){
                low = middle +1;
            } else if (b< a[middle]){
                high = middle -1;
            } else { // The element has been found
                return true;
            }
        }
        return false;
    }
}

That’s it for the sorting and searching methods. Hope you’ve learned a lot. The APCS exam won’t require you to memorise these pieces of code. However, it would still be a good idea to know what each one looks like so that you can recognise which is which when you see them. It’s near the end of the school year. Keep on going strong!

As always, if you have questions, please ask either in the comments below, fill out a contact form, consult other netizens on StackOverflow or some other forum and ask your teacher.

Lieutenant out!

Published by

LtDemonLord

Life's too short to let your brain go to waste.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s