Searching

Searching involves looking through a list of items and finding one (or more) of those items. There are two major algorithms (and many others) used to find an item(s) in a list. The linear search looks through a list one element at a time (sequentially). It is not a very efficient search algorithm, and should only be used when your list is relatively small. The binary search is very fast at finding an element, but the data elements must be unique and must be in order (sorted).

Examples:




Looking through an array (linear search)

// looks through the list looking for itemToFind
// if found, it returns its position in the list
public int search(String [] list, String itemToFind)
{
    // look through the list to find itemToFind
    for (int i=0; i<list.length; i++)
    {
        if (list[i].equals(itemToFind))
            return i; // returns the index of where we found it	
    }
	
    return -1; // item not found
}



Looking through an ArrayList (linear search)

// looks through the list looking for itemToFind
// if found, it returns its position in the list
public int search(ArrayList list, String itemToFind)
{
    // look through the list to find itemToFind
    for (int i=0; i<list.size(); i++)
    {
        if (list.get(i).equals(itemToFind))
            return i; // returns the index of where we found it	
    }
	
    return -1; // item not found
}




Looking through an array (binary search)

String [] list = {"Tom", "Sue", "Adam"};

Arrays.sort(list);

int x = Arrays.binarySearch(list, "Adam");
if (x >= 0)
{
    // found it, so do whatever

}




Looking through an ArrayList (binary search)


ArrayList list = new ArrayList();

list.add("Tom");
list.add("Sue");
list.add("Adam");
etc.

Collections.sort(list);

int x = Collections.binarySearch(list, "Adam");
if (x >= 0)
{
    // found it, so do whatever

}