Linear Search
(First of all note that "linear search"', and "sequential search" are exactly the same thing.
This kind of search is a straigh-forward way to look for an certain "key" value in an array (or indeed a list) by looking at one element at a time, in order, until it is found (or not found).
If, while doing the search the key is found, the element where it is located is immediately returned, and the search stops. This is nice in that it doesn't waste time continuing to loop through the array once the key is found.
If the key happends to be not found, -1 is returned. So the code making use of this method would have an if/else block checking to see if the returned value was -1, and if so, that means the key was not found; whereas if a number other than -1 is returned, that is the element where the key value is to be found.
public int sequentialSearch(String arr[], String key){
for(int i = 0; i < arr.length; i++){
if(arr[i].equals(key)){
return i;
}
}
return -1;
}
Example array of Strings. (Note that it does not need to be sorted for the linear search to work.)
[0] [1] [2] [3] [4] [5] [6] Sue Bill Meg Charles Phil Sally Jane
So if we were looking for the key value Charles, we would look at element 0 - is it Charles? No. So then we would look at element 1, and 2, and so on, asking is it Charles? The answer would continue to be No, until we got to element 3. At element 3 we ask is it Charles - And the answer is Yes. So at that point we return the element number, which is 3. Note that in this case we never get to the last return statement, which is waiting to return -1 if no element is found.
Whereas if we were looking for a value which is not in the array, such as John, we would look in the 0th, the 1st, the 2nd element and so on, but never get to the point where arr[i].euqlals(key), so the for loop would end after i got up to the length of the array, and the last line of the method would execute, which is to return -1.
Why we return the element number, not the key
The reason we return the element number is that knowing where in the data structure the key being searched for is located is usually very useful. This is because usually, - at least in Object Oriented Programming (OOP) - there is other data associated with the search key that we are out to get.
So rather than an array of Strings, a more likely example, similar to the one above, would be searching through an array of, say, Student objects. We look for the Student with the name "Charles", but what we are really after is, for example, his grade, or maybe his parent's email address, etc. So when we find the index where Charles resides in the array, using that index we can then get access to his grade, etc.
Here is a full example of something like that:
1public class SequentialSearchOfObjects { 2 public static void main(String[] args) { 3 Student sue = new Student("Sue", 9, "betty@gmail.com"); 4 Student bill = new Student("Bill", 12, "billsDad@hotmail.com"); 5 Student meg = new Student("Meg", 8, "helloKitty@yahoo.com"); 6 Student charles = new Student("Charles", 10, "bob@bob.com"); 7 Student phil = new Student("joan", 9, "drJoan@dr.com"); 8 9 Student [] students = {sue, bill, meg, charles, phil}; 10 11 int x = sequentialSearchByName(students, "charles"); 12 System.out.println("Charles is in grade: " + students[x].getGrade()); 13 } 14 15 public static int sequentialSearchByName(Student [] arr, String keyName){ 16 for(int i = 0; i < arr.length; i++){ 17 if(arr[i].getName().equals(keyName)){ 18 return i; 19 } 20 } 21 return -1; 22 } 23}
Binary Search
The binary search is a much more efficient way of searching than the linear search. In the binary search we reduce the possible number of elements which might contain the key by a half with each loop. So the maximum number of times we will have to loop looking for a key is log N, with N the number of elements. For example, we could locate a key value in an array of 1,000,000 in 20 steps. This is becasue log 1,000,000 - assuming base 2 - is 20.
(And do note that, as computer scientists, when talking about logarithmic efficiency, we assume base 2. So the efficiency of the binary search is indeed written as log N, rather than log2 N.)
The basic idea is that if we have an array of a certain size, and the values are ordered from least to greatest, if we pick the middle element and that is not what we are looking for, and we compare that value to the one we are looking for, we can eliminate the necessity of seraching half of the array. You see if the value we are looking for is greater than that middle value, we know that we don't have to worry about looking through the first half. In which case we take the second half, pick the middle element of that, and repeat the process of disregarding the half than cannot contain the key value due to it being greater or less than the middle value.
This is the "Non-recursive" or "Iterative" Binary Search. You'll note that there are two ways of looping: 1. iteration - the normal way, with for or while loops -, and 2. recursive, a more sophisticated way of achieving looping. We will look at a recursive binary search later on.
Remember that in order for this to work, the array needs to be sorted.
public int binarySearch(int arr[], int key){
int low =0;
int high = arr.length -1;
while(low <= high){ // Keep on looking for the key until the low and the high cross
int mid = (low + high) / 2; each other - if that does happen, it means the key was not found.
if(key == arr[mid])
return mid; // This is what will happen if/when we find the key in the array.
else if(key < arr[mid])
high = mid - 1; // Since the arr[mid] value is less than the key, we can eliminate
else looking at the left side of the remaining elements
low = mid + 1; // i.e. the arr[mid] value is greater than what we are looking for,
} so we can eliminate looking at the right side of the remaining elements
return -1;
}
A classic video explaining the binary search.
And a new one by me: