Binary/Sequential Searches

Question

I'm trying to write a program that conducts a sequential search and a binary search in an array called items that has 10000 sorted random int values. A second array called targets is loaded with 1000 int values (500 values from the items array and 500 values that are not in the items array).

Basically, the search needs to go through the items array to look for int values in the targets array. This is my code:

  import java.util.*;

 // Loads two arrays with integers
 // Searches the arrays using sequential search and binary search
 // Compares the time for each search

public class Searches {

private int items[], targets[];

public Searches() { 

    this.items = new int[10000];
    this.targets = new int[1000];
}

public void loadItemsAndTargets(){

    int nextValue = 100;
    int index = 0;

    Random generator = new Random(1); 

    items[0] = nextValue;

    /* load the items array with items to be searched through */

    for (index = 1; index < items.length; index++){
        nextValue = nextValue + generator.nextInt(100);
        items[index]= nextValue;
    }

    /* load the targets array with target values that will be searched for within
     * array items, and target values that are not within array items
     */

    index = 0;

    while (index < targets.length){
        targets[index] = items[index*10];
        targets[index+1] = generator.nextInt(100);
        index = index + 2;
    }      
}

public int sequentialSearch(int target) {
    /* Using the sequential search algorithm, search the items array for the target value passed
     * If found, return the index in the items array, otherwise return -1
     */
    this.loadItemsAndTargets();

    int key = target;
    int index;

    boolean found = false;

    index = 0;
    while ((!found) && (index < items.length)) 
        if (key == target)
            found = true;
        else
            index = index + 1;

    if (!found) 
        index = -1;
    return index;
}       

public int binarySearch(int target){
    /* Using the binary search algorithm, search the items array for the target value passed
     * If found, return the index in the items array, otherwise return -1
     */
    this.loadItemsAndTargets();


    target = targets.length;
    int key = target;
    boolean found = false;
    int guess = 0;
    int low = 0;
    int high = items.length - 1;
    while ((!found) && (low < high)) {
        guess = (high+low)/2;
        if (key == items[guess]) 
            found = true;
        else if (key < items[guess])
            high = guess - 1;
        else
            low = guess + 1;

        if (!found)
            return - 1;
    }

   return guess;
}
public static void main(String[] args) {
    int index = 0;
    Searches searcher = new Searches();
    searcher.loadItemsAndTargets();

    /* call the method that searches array items 
     * for each of the values in array targets
     * using the sequential search algorithm
     * print the approximate elapsed time in milliseconds
     * For the FIRST FIVE searches print out the index 
     * where target value was found or print -1 if it was not found 
     */


    long startTimeSequential;
    startTimeSequential  = System.currentTimeMillis();

    System.out.println(searcher.sequentialSearch(index));

    long endTimeSequential;
    endTimeSequential = System.currentTimeMillis();

    long totalTimeSequential;
    totalTimeSequential = endTimeSequential-startTimeSequential;
    System.out.println("sequential search time: " + totalTimeSequential + " milliseconds");

    /* call the method that searches array items
     * for each of the values in array targets
     * using the binary search algorithm
     * print the approximate elapsed time in milliseconds
     * For the FIRST FIVE searches print out the index 
     * where target value was found or print -1 if it was not found 
     */
    long startTimeBinary;
    startTimeBinary = System.currentTimeMillis();

    System.out.println(searcher.binarySearch(index));

    long endTimeBinary;
    endTimeBinary = System.currentTimeMillis();

    long totalTimeBinary;
    totalTimeBinary = endTimeBinary - startTimeBinary;
    System.out.println("binary search time: " + totalTimeBinary + " milliseconds");
 }      
}   

EDIT: The output should be this >

395

986

-1

14

-1

sequential search time: 40 milliseconds

395

986

-1

14

-1

binary search time: 0 milliseconds

Answer 1

Your sequentialSearch is all wrong, you are not even accessing the array in it.

Both your search method call loadItemsAndTargets. It should only be called once

binarySearch only works on sorted array. Your arrays are not sorted.

Even if you correct all of these mistakes. Beware that your array will contain duplicates. So if try to compare the index between sequentialSearch and binarySearch they may not match unless your binarySearch returns the lower bound

Answer 2

Sometimes it is easier to write the code when you have a very strong grasp of the searching techniques at hand. With that in mind, I'll repeat what you probably have heard just in case it wasn't explained well.

A sequential search is simple:

1. Set the starting index just before the beginning.
2. If there is a "next" item, check the next item to see if it matches.  
2a. If it does match you found the item in your collection.
2b. If it does not match update the starting index to the item you just checked and continue at step 2.
3. If there is no next item, then you searched everything without finding your item.

A binary search is also simple:

1. If the unsearched part of your list is empty, then determine you didn't find the item.
2. If the unsearched part of your list is just one element, then check the element to see if it matches the lookup item.
2a. If id does match, you found the item in your list.
2b. If it does not match, the item isn't in your list.
3. If the unsearched part of your list is more than one element, find the element closest to the middle. It is ok to divide two element lists like {2, 4} into {2} 4 {} where 4 is the middle.
3a. If the middle matches the lookup item, you found the item in your list.
3b. If the middle is larger than the lookup item, select the "smaller" side list and repeat the process.
3c. If the middle is smaller than the lookup item, select the "larger" side list and repeat the process.

The advantage of a sequential search is that your item will eventually be found, even if the list is not sorted. The advantage of a binary search is that you will find your item much faster but the list must be sorted. For example, a million item list will take on average half a million comparisons to find an item by sequential search; but, a binary search will take only about twenty comparisons. That is because each comparison in a binary search throws away half of the remaining possibilities while each comparison in a sequential search only throws away one possibility.