Binary Search vs Linear Search

You will learn :

• Binary search
• Linear Search
• Where to use Linear Search
• Where to use Binary Search
• How Binary Search Works

Linear Search :

• It used on unsorted List 
• It is very slow for large Lists
• Its easy to write code for Linear Search
• Should be only used if the list is a few elements long

Code :

1:  public class Search {  
2:         
3:       public static void main(String args[]){  
4:            int array[] = {1,5,9,11,25,90,122};  
5:            int key = 122;  
6:     
7:      Search.LinearSearch(array,key);  
8:       }  
9:         
10:       public static void LinearSearch(int array[],int key){  
11:            int last = array.length-1;  
12:              
13:            for(int i = 0; i < array.length;i++){  
14:                 if(array[i] == key){  
15:                      System.out.println("The key found at index : "+i);  
16:                      return;  
17:                 }else if(i == last)  
18:                  System.out.println("Not in the Array");  
19:                 else System.out.println("Searching.....");  
20:            }//loop  
21:              
22:       }//method  
23:         
24:  }  
25:    

Explanation :

                     In this program an array is searched for a specific value. A for loop is used to go through and check each element if the element is found at any location in the array the loop breaks and message is displayed. In the other case the message is displayed that "Not i  the Array".

Binary Search:

• Cuts the array half after each iteration
• Suitable for searching in large Lists
• Used only if the List is large enough
• Faster than Linear Search
• A bit complex to code

Code :

1:  public class Search {  
2:         
3:       public static void main(String args[]){  
4:            int array[] = {1,5,9,11,25,90,122};  
5:            int key = 122;  
6:     
7:      Search.BinarySearch(array,key);  
8:       }  
9:         
10:       public static void BinarySearch(int array[],int key){  
11:            int last = array.length-1;  
12:            int first = 0,mid = (first+last)/2;   
13:              
14:            for(int i = 0; first <= last;i++){  
15:                 mid = (first+last)/2;  
16:                 if(array[mid] == key){  
17:                      System.out.println("The key found at index : "+mid);  
18:                      return;  
19:                 }else if(array[mid] > key)  
20:                      last = mid - 1;  
21:                     
22:                 else if(array[mid] < key)  
23:                      first = mid + 1;  
24:                 else if(i == array.length-1)  
25:                      System.out.println("Not in the Array!!!");  
26:                 System.out.println("Searching......");  
27:            }//loop  
28:              
29:       }//method  
30:         
31:  }  

Explanation :

                    Look at line# 16 if middle element of the array is equal to the the search number then Display the message "Found the key" and break the loop. At line#19 if middle element is greater than key then the second half of the array is ignored and the end of the array shifts at mid - 1. Similarly At line# 22 if middle element is less than the key than first half is ignored and first is shifted to 'mid + 1'. Note that your array must be sorted in the ascending order first to apply this algorithm.
    Here is an image which may also help :

I hope this post have cleared out the problems and questions related to Linear and Binary Search if not Comment the question below. Like us for more!!!