Linear Search and Binary Search

SEARCHING ALGORITHMS

Searching algorithms are used to retrieve data or information which is stored in data structures. We generally store data and its information in data structures – arrays, link lists, hash tables or some other methods. Now when we want to search for a particular element is what searching algorithm is all about.

For example, In order to go to a particular topic or a chapter in a heavy book consisting of 2000+ pages, seems to be a tedious task ; We directly go to index section of the book, which further leads us to the desired content through various ways. Searching can be done in two ways- 1.1 LINEAR SEARCH

Linear Search is a method used for finding a desired data within the data structure in sequential order, i.e.  it goes on checking one by one in a ordered way from start to end.

How it works?

• It checks sequentially each element present in the array for finding the desired element until a match is found.

BASIC ALGORITHM:-

1. Set index (i) to 0.

2. Using for loop, traverse the array.

3. In every iteration, target element is to be compared with the current value of the array.

4. If value matches, return the current index of the array.

5. If value doesn’t matches, move to next element in the array; Set i=i+1,

6. Go to step 3.

PSUEDOCODE:-

int LINEAR_SEARCH(int *arr, int size, int target)

{

For (int index=0; index<size; index++)

If (arr[index] ==target)

Return index;

Return -1;

}

Example-1:-

Input:  arr[] = {7,5,9,6,10}

Size of the array: 5

Target element: 6   Output: The desired element 6 is present in index 3.

Example-2:-

Input:  arr[] = {9,4,3,2,8}

Size of the array: 5

Target element: 1    Output: -1.

The desired element 1 is not present in arr[].

TIME COMPLEXITIES:-

• BEST CASE:  if the targeted element is present in the beginning of the array. When we are able to find the required element in first search only. In that case, Number of iterations =1. • WORST CASES: Element not present in the whole array as given in example.2. Therefore, number of iterations = n+1

We search n elements n times and in n+ 1 time come out of for loop.

Time complexity: O(n)

1.2 BINARY SEARCH

Binary Search is highly efficient search algorithm which helps to find the position of target value within a sorted array. It is only efficient when the elements are stored in sorted array.

PROCEDURE:

• In a sorted array, the search commences by comparing the middle element of the array with the target element.

• If the middle element matches with the target element, its position in the array is returned.

• If the target value is less than the middle element, then in left half of the array search continues otherwise search takes place in the right half.

ALGORITHM:

1. Set L to 0 and R to n-1.

2. If L>R, the search terminates as unsuccessful.

3. Set m(the position of the middle element) to the floor(the largest previous integer) of (L+R)/2

4. If T=Am, the search is done; return m.

5. If T>Am, set L to m+1 and go to step2.

6. If T<Am, set R to m-1 and go to step2.

PSUEDOCODE:

int BINARY_SEARCH(int arr[], int l, int r, int target)

{

int m;

while (l<=r)

{

m= (l+r)/2;

if (arr[m]==target)

return m;

If (arr[m]<target)

l=m+1;

else

r=m-1;

}

Return -1;

}

Example:

Input:  arr[] = {2,5,8,12,16,23,38,50,72,91}

Target element: 23  Here ,

m= (l+r)/2 = (0+9)/2 = 4

if (a[m]==target) ✖✖

if (a[m]<target)    ✔✔

l = r+1; Here,

m= (l+r)/2 = 7

if (a[m]==target) ✖✖

if (a[m]<target)    ✖✖

if (a[m]>target)   ✔✔

r =m-1; Here,

m= (l+r)/2 = 5

if (a[m]==target) ✔✔

Output:  The desired element 23 is present in index 5.

TIME COMPLEXITIES:-

Recurrence Relation: T(n) = T(n/2)+1    if n>1

T(n)=1 if n=1

So, according to master’s theorem, T(n)= O(log2 n)

1. COMPARISION:

 BINARY SEARCH LINEAR SEARCH Binary Search works only in arrays.   Arrays has to be sorted.   Binary Search access data in a random order. Input data needs to be stored (mandatory).   Time Complexity= O(log2n). Linear Search can work in any data structure – arrays, linked lists etc. Works in both sorted and unsorted arrays.   Linear Search does sequential search.   Not required to store input data.   Time Complexity= O(n).

Therefore, when the array is sorted binary search performs much effectively than the linear search but in case of unsorted array only linear search can be performed.