Searching Techniques

Linear & Binary Search

Linear Search:

Linear search is also known as sequential search algorithm. It is the simplest searching algorithm. In Linear search, we simply iterate the list completely and match each element in the array with the element to be searched. If the match is found, then the location of the item is returned; otherwise, the algorithm returns NULL.

Algorithm:

Step 1: Start.
Step 2: Declare an array and accept the element to be searched as key.
Step 3: Traverse the array until the number is found in that array.
Step 4: Return the index position of the array element if key is found.
Step 5: Return -1 if the key element is not found in the array.

This is how the code based on this algorithm looks like:

public class Main
{
    //Function to search for element key in an array:
    static int linearSearch(int arr[], int key){
        
        //Writing a for loop to traverse the array
        for(int i=0; i<arr.length; i++){
            
            //Checking if the each element is equal to key element
            if(arr[i] == key){
                return i;
            }
        }
        
        //If the element is not present in the array: 
        return -1;
    }
 public static void main(String[] args) {
  int arr[] = {12,5,10,15,31,20,25,2,40};
  
  //Best case, where the target is the first element of the array:
  System.out.println(linearSearch(arr,12));
  
  //Average case where element is present in the array:
  System.out.println(linearSearch(arr,20));
  
  //Worst case where element is not present in the array:
  System.out.println(linearSearch(arr,100));
 }
}

Let us try to understand this better with the help of a diagram:

Compares the value of key with each element in the array till the key is found. Source

What about the time complexity for linear search?

Time and Space Complexity of Linear Search

Where do we use linear search?

1. When the data size we are working on is small, linear search is ineffective in terms of its time complexity for larger data size.
2. When the data is unsorted: Efficient algorithms like binary search cannot be implemented if the data is unsorted. Hence linear search is used in these cases.
3. Linear search can also be used in multi-dimensional arrays whereas binary search is used in one-dimensional arrays.

Binary Search:

Binary search is the search technique that works only on sorted lists. If the array is not sorted we need to sort it by using any of the sorting techniques. The list is divided into two halves, and then the element is compared with the middle element of the array. If the match is found then, return the middle element location.. Otherwise, search either halves depending on the the result.

Algorithm:

Step 1: Begin with the mid element of the whole array as a search key.

Step 2: If the value of the search key is equal to the item then return an index of the search key.

Step 3: Else If x is greater than the mid element, then x can only lie in the right half sub array after the mid element. So we recur for the right half.

Step 4: Else x is smaller recur for the left half.

Implementation of Binary Search:

1. Iterative Method
2. Recursive Method

//Iterative binary search:
public class Main
{
    //You want to search for target element in a sorted array:
    static int binarySearch(int arr[], int target){
        int low = 0;
        int high = arr.length - 1;
        while(low<=high){
            //You will find the mid index & compare it with target element.
            int mid = (low + high)/2;
            if(arr[mid]==target){
                return mid;
            }
            //If target is smaller than mid, search the left part.
            else if(arr[mid]>target){
                high = mid - 1;
            }
            //If target element is greater than mid, search the right part.
            else{
                low = mid + 1;
            }
        }
        return -1;              //If element is not present
    }
 public static void main(String[] args) {
  int a[] = {1,2,3,4,5,6,7,8};
  //Calling the method
  System.out.println(binarySearch(a,8));
 }
}

//Recursive binary search:
public class Main
{
    static int binarySearch(int arr[], int key, int low, int high){
        int ans = -1;
        if(low > high){
            return -1;
        }
        //Calculating the index of the mid element 
        int mid = (low + high)/2;
        
        //If key is equal to the middle element.
        if(arr[mid] == key){
            return mid;
        }
        
        //If key is lesser than mid, call function for left sub array
        if(key<arr[mid]){
            ans = binarySearch(key, arr, low, mid-1);
        }
        
        //If key is greater than mid, call function for right sub array
        if(key>arr[mid]){
            ans = binarySearch(key, arr, mid+1, high);
        }
        
        //returning the index of the element if it is present.
        return ans;
    }
 public static void main(String[] args) {
  int a[] = {1, 2, 3, 4, 5, 6, 7, 8};
  //Calling the method.
  System.out.println(binarySearch(a,8,0,7));
 }
}

Let us take an example and see how binary search works. Assume we have a sorted array of 15 elements [0,2,4,6,8,10,12,14,16,18,20,22,24,26,28]. We are searching for 18 in this array:

Steps and Comparisons showing Binary Search. Source

What about the time complexity?

As the data size keeps on reducing, we get an average time complexity of O(log n).

Time and Space Complexity of Binary Search

Applications of Binary Search in Problem Solving:

• To find if is an element is square of an integer in that list
• Find the first value >= to x in a given array of sorted integers
• Find the frequency in an array of integer of a given target value

Real life applications of binary search:

1. Dictionary
2. Debugging a linear piece of code
3. Figuring out resource requirements for a large system
4. Find values in sorted collection
5. Semiconductor test programs
6. Numerical solutions to an equation

Upcoming topics for the blogs:

For queries regarding the content, please drop a mail to loop@cumminscollege.in Links for in-depth studying and practice problems are sent via mail to students of the college on the date of publishing of the blog by Loop Club. The content is a part of DSA Bulletins started by Team Loop, to provide thorough knowledge and facilitate the learning of new topics of DSA. We are a group of students who are passionate about CP and DSA and want to create awareness and help students in the above topics.