## Searching for a Number

Just like sorting, trying to find a number in a group of them is not always as easy as it may seem. Searching algorithms have also been studied for many years with many books being written on the subject. We are going to look at the linear search and the binary search algorithms. Both of these algorithms rely on the array already being sorted to find the item.

## Linear Search

Linear search is one of the most simple searching algorithms. It is exactly how you might think of programming one yourself. You start at the beginning of the array and move down the list until you find item.

```
public int linearSearch(int find, int[] a){
// start going through the array
for(int i = 0; i < a.length; i++){
// if we find the number, tell the user which spot
if(a[i] == find){
return i;
}
}
// send back -1 if we never found the item
return -1;
}
```

## Binary Search

Since we already know that the array is sorted, we can take advantage of it. Instead of looking through the entire array, why don't we try looking at the middle each time. We could get lucky and that might actually be the number we are looking for. If the number is bigger than the middle, we know it most be in the later half of the array. If it is smaller than the middle number, it should be in the early half. We will keep doing this until we find it or not.

```
public int binarySearch(int find, int[] a, int start, int end){
// if we have come to the point where start > end, we cant find it
if(start > end){
return -1;
}
// calculate the middle number in the array
int mid = (end+start)/2;
// if we found it, return where it is
if(a[mid] == find){
return mid;
// if the number is smaller, look in the left half
}else if(find < a[mid]){
return binarySearch(find, a, start, mid-1);
// if the number is bigger, look to the right
}else{
return binarySearch(find, a, mid+1, end);
}
}
```