Primitive Data Search - algorithms basic 01

Searching is a common way to find the target data in a data group. The data group contains the same data type.


Note that Java SE API provides a simple way of searching.
Arrays.binarySearch( ... ) 
Collections.binarySearch( ... )
check: Java SE API - Oracle Java Platform SE 6.0
     - java.util.Collections
     - java.util.Arrays


But thinking deeper of what is inside the method helps us to understand more about searching  and to implement with other programming languages.


There are two common approaches:
1 Linear Search - go and compare with each item in a linear way
2 Binary Search - go and  compare with the middle item of each iteration


Example:
searching through a given group of integers with 10 elements:
int a[] = { 7, 5, 8, 2, 9, 0, 3, 6, 1, 4 };


we need to find out if this group has 20. if yes, show the index of 20, otherwise the index of 20 set to -1.
(0 is the beginning index of an array, so -1 means it is not in the array)


So how do we perform the search?
We aim to minimize the comparisons to find the target data fast.
Let's compare 2 basic search algorithms.


1 Linear Search
The linear search needs to go through each item, unless we are lucky that the first item is our target.
Here, it is obvious that there is no 20 in the integer array.
So, we need to perform 10 comparisons.
Code:

1. int a[] = { 7, 5, 8, 2, 9, 0, 3, 6, 1, 4 };
2. int target = 20;
3.   //try to change target to any value in the array
4. int found=-1;
5. for(int i=0;i<a.length;i++){
6. if(a[i]==target){
7. found=i;
8. }
9. }
10. System.out.println(found);

2 The Binary Search
The binary search needs roughly 3-4 comparisons to find 20
Well, first we need to sort the given array, whether in ascending or descending order, it is up to you.
int a[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
Since we know the order is ascending, let us begin the begin the Binary Search.
Steps:

1. find the element in the middle which is 4, 4 is less than 20, now we know anything on the left side of 4 does not have 20, so we move on.
2. find the element in middle of the right hand side of 4 which is 7, 7 is less than 20, we move on.
3. comparing 20 with 8 ...
4. comparing 20 with 9 ...   End of story!!!

Code:

1. int a[] = { 0, 1, 2, 3, 4, 5, 6,7,8,9 };
2. int target = 20;
3.   //try to change target to any value in the array
4. boolean isFound = false;
5. int len = a.length;
6. int begin = 0;
7. int end = len - 1;
8. int mid = (end - begin) / 2;
9. while (!isFound&&begin<=end) {
10. if (a[mid] == target) {
11. isFound = true;
12. break;
13. } else if (a[mid] < target) {
14. begin = mid+1;
15. } else {
16. end = mid-1;
17. }
18. mid = (end + begin) / 2;
19. }
20. System.out.println(isFound+" - "+mid);

Linear Search or Binary Search?
Linear Search does not require pre-sort the elements, and it is easy to code, maintain and debug. The time complexity of Linear Search is O(n). 


Binary Search requires pre-sort the elements, but it saves time in finding the target. The line of code are longer, so it takes time to code, maintain and debug. The time complexity of Binary Search is O(log2n)

Some people may think it doesn't matter which algorithm we perform here. Yes.

But if we are searching an element within a group with 1,000 or even 1,000,000 elements.

Binary Search helps to save heaps of time in such a case.

To Search Other Data Types:

Just like an integer array, you can easily implement the above algorithms with primitive data types char, float, double, short, long, byte.


For String, the String class implements Comparable interface, when we compare 2 Strings we use compareTo method.


For Object, the class must implement the Comparable interface, and we need to override the compareTo method.


Other references: 
Algorithm - Wikipedia
Analysis of algorithms - Wikipedia
Time complexity - Wikipedia
Binary search algorithm - Wikipedia