Linear search Vs. Binary search | Data structure

A linear search algorithm search one item at a time, without jumping to any item.

  1. The worst case complexity is O(n).
  2. Time taken to search elements keep increasing as the number of elements are increased.

 

A binary search however, cut down your search to half as soon as you find middle of a sorted list.

  1. The middle element is used to check if it is greater than or less than the value to be searched.
  2. Accordingly, search is done to either half of the given array list.

 

 

Linear Search

Binary Search

Binary search requires the input data to be sorted

 

linear search doesn't

Binary search requires an ordering comparison

 

linear search only requires equality comparisons

Binary search has complexity O(log n)

linear search has complexity O(n)

Binary search requires random access to the data

linear search only requires sequential access

 

Contributor's Info

Created:
0Comment
Binary Search | Data structure
  1. Binary search is a fast searching algorithm as compare to linear search algorithm.
  2. Binary search looks for a particular item by comparing the middle item with the searched value. If a match occurs, then the index of item is returned.
  3. If the middle item is greater than the item, then the item is searched in the sub-array to the left of the middle item. Otherwise, the item is searched for in the sub-array to the right of the middle item.

Example:

10

14

17

21

25

29

31

35

       0                 1                    2                   3                    4                   5                    6                   7

 

In the above array we have to search for an element 29.

 

Some terms related with binary search:-

Low=0                 High=7

Mid=( low + high )/2 = (0+7)/2 = 3.5 = (Approx) 3   

The value present in index 3 is 21

 

Step1: we will compare the mid value 21 with the searched value 29.

          29>21 so  we will take the forward part of 21 and skip the other one.

21

25

29

31

35

 

         3                            4                                5                                6                                 7

 

Step 2: Again we have to calculate the low, high and mid value.

          Low=mid+1=3+1=4                 High=7

          Mid=( low + high )/2= (4+7)/2 = 5.5 = (Approx) 5

          The value present in index 5 is 29

          We are searching for the value 29 and we got it.

 

So, the searched value 29 is present in the index value of 5.

 

Implementation:

Procedure binary_search

   A ← sorted array

   n ← size of array

   x ← value to be searched

 

   Set lowerBound = 1

   Set upperBound = n

 

   while x not found

      if upperBound < lowerBound

         EXIT: x does not exists.

  

      set midPoint = lowerBound + ( upperBound - lowerBound ) / 2

     

      if A[midPoint] < x

         set lowerBound = midPoint + 1

        

      if A[midPoint] > x

         set upperBound = midPoint - 1

 

      if A[midPoint] = x

         EXIT: x found at location midPoint

   end while

  

end procedure.

 

Note:

  1. Binary search is also known as “Half- Interval search”.
  2. Time complexity :
  • Best case performance of binary search = O (1)
  • Worst case performance of binary search = O (log n)
  • Average case performance of binary search = O (log n)

 

Applications:

Binary search algorithm is mostly used for making “Binary search tree” and “Hashing techniques”.

 

Drawback:

For performing binary search technique the array must be in sorted order. Binary search technique can’t be used in unsorted array.

 

But as compare to linear search , Binary search is preferable.

 

Contributor's Info

Created: Edited:
0Comment
Binary Search algorithm

Binary searching is technique to search specified element in a shorted array of Integers.It is mostly used in case of searching when there is a given shorted array.Its time complexity is O(log N).

Algorithm:

int Binarysearch(int a[],int size,int key){
int low=0,high=size-1;
boolean find=false;
int mid=0;
while(low<=high){
 mid=(high+low)/2;
if(key==a[mid]){
    find=true;
    break;
}
else if(key<a[mid])
    high=mid;
else
    low=mid+1;
}
if(find)
    return mid;
else
    return -1;
}

 

Contributor's Info

Created:
1Comment
shweta @shweta1920 30 Apr 2017 12:09 pm

i think u should write "sorted" instead of "shorted"