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!

2/9/13 Polymorphism

Have you ever wanted to create a arraylist that can only contain objects with a certain method? Believe it or not, this is completely possible using an idea called Polymorphism. You can make your arraylist only contain a certain interface, making it be so that all classes that implement the interface can be put into your arraylist. This has many advantages to it, including the ability to use the sort method without risking an error because an object in the list dose not have a compareTo method. This can also be used for objects in a game that are destroyed when they collide. In this scenario, you can have all the objects implement a collidable method and then create an arraylist of collidable objects. I want to point out that you can also do this with abstract super classes. If you have a supperclass called shape, subclasses for different shapes, and an arraylist of type shape, you could use a for each loop and print the area of each shape. I am sorry that this article is sort of short, but I have a lot of homework to get done. Anyway, I hope you learned a thing or two about java and Polymorphism.

2/3/13 Interface

Do you know where spotify gets it's music from? Well, there are is a list of methods that it uses to find your music for you. Whether or not you know how or where spotify gets its music from, it still will play music for you. This is called an Interface, and as you may have guessed,  you can use them in Java.

In Java, an Interface is a piece of code that you write that will give you a list of methods which the classes that implement it must include. Please note that this is just a list of methods, and not the methods themselves. If you implement an Interface into your code's class, you are saying that this class will define and write all the methods that the interface lists. This could be useful if you are writing classes for different shapes on a grid. Each shape could inherit from a super class that gives you the coordinates of the shape, but the area of different shapes is determined in different ways. This means that you should have an interface that says that all member classes must have a get area method. To give the shapes this Interface, you will type:

class name implements size{

where name is the shape that you want to implement this interface for. The size interface code would look something like this:

public interface size{
 public double getArea();
}

please note that an interface can have more than one method inside of it. This would look something like this:


public interface size{
 public double getArea();
 public void grow(int factor);
 public void shrink(int factor);
}

I hope that you have learned a thing or two about interfaces in java, and feel free to ask me questions in the comments.