2/16/13 Search basics

Lets say that you have a bunch of containers, each of which is a different size and you are looking for a container with a certain size. How would you find it? There are a couple of ways that you could go about doing this; you could look at the containers one at a time until you find one that is the correct size, or you could sort the jars by their size and then use the fact that the jars are sorted to find the jar you are looking for quickly. You may be wondering how this ties into computer science, and the answer is that you use these same basic ideas to find something inside of an array.

Lets say that you have an array of integers and you are looking for a location where you can find the number five. If the array is unsorted, you could find the index by using a for loop to go through each index until you find the number five. A generic method that will return the index of an integer in an integer array would look something like this (remember that if the index can not be found, a search algorithm will return -1):

public int search (int[] arr, int goal){
 for(int i = 0; i<arr.length; i++){
  if(arr[i]==goal){
   return i;
  }
 }
 return -1;
}

This is what is commonly known as a linear search, and is the only way to find something in an unsorted array. If your array is already sorted for you, there is a much faster way to find what you are looking for; through a binary search. A binary search will start in the middle of the array and compare what it is looking for (lets be looking for 5 again) to the middle value of the array. If 5 is larger than the middle value, you know that the index of 5 must be larger than the middle value. If 5 is smaller than the middle value, you know that the index of 5 must be smaller than the middle value. You then take this information and look for the middle index of your new selection of values and repeat the process until you find the number that you are looking for. A binary search algorithm is a little bit more tricky to code, but it would look like this (for a binary search, if the element is non existent, the search returns -1 minus (-1 times the index where it would have been)):

public int binarySearch (int[] arr, int goal){
 int min=0;
 int max=arr.length-1;
 while (min<=max){
  int middle = min+((max-min)/2);
  if(arr[middle]>goal){
   max=middle;
  }
  else if(arr[middle]<goal){
   min=middle;
  }
  else{
   return middle;
  }
 }
 return -middle;
}

So, hopefully you have learned a thing or two about searching and java. Thanks for reading!