Be the first user to complete this post

  • 0
Add to List
Beginner

382. Linear Search vs Binary Search

Earlier we have seen linear search and binary search and how these work individually, In this article we will compare these two search algorithms. If you are new to these, please read the prerequisites below-

Prerequisites:

SNo Linear Search Binary Search
1Works with a sorted or unsorted array.Works with sorted arrays only
2Simple scan – iterates and compares one item at a time, either left to right or vice versa.Removes half of the items after each comparison until the element is not found
3For an array, iterate from the beginning to the end, and test each item in the array
After 1st iteration, N/2 items remain (N/21)
After 2nd iteration, N/4 items remain (N/22)
After 3rd iteration, N/8 items remain (N/23)
4

static void search(int [] input, int x){

        for (int i = 0; i <input.length ; i++) {
            if(x==input[i]) {
                System.out.println("Element " + x + " is found at index: " + i);
                return;
            }
        }
        //if here means x is not found
        System.out.println("Element " + x + " is not found in array");
    }

If(mid_element==key)
  return true;
else if (mid>key)
  do a recursive search on the right half of the array.
else
 do a recursive search on the left half of the array.

5Time Complexity: O(N)Time Complexity: Log2N

Please see the code below and run on IDE for better understanding.

Output:

Linear Search.....Element 14 is found at index: 5
Binary Search.....Element 14 is found in array at index: 5

Linear Search.....Element 21 is not found in the array
Binary Search.....Element 21 is not found in the array