Recent Post

Searching

Searching is a technique to search a array element.
There are two type of searching:-

* Linear Searching
* Binary Searching

1) Linear Searching:-Sequential Search is made over all item one by one.
     Algorithm:-
                   
Step 1 :- i=0
Step 2 :- if i>n , goto step 7
Step 3 :- if A[i]=x , goto step 6
Step 4 :- i=i+1
Step 5 :- Go to step 2
Step 6 :- Print element x found at i
Step 7 :- Print element not found
Step 8 :-Exit

 i=0
x=16
A[i] = A[0]=4
A[i] = x or whether      A =16
i = 0+1=1
A[i]=16
i=2        A[2]=16
.
.
.
.
.
.
i=4        A[4] = 16

The element 16 found at 4 

Exit

2) Binary Searching:-

Fast search algorithm with time complexity of o(log n)
Based on divide and conquer
Data item should be sorted order.

Example:-
( Find location of value 14)
 
 While low =< high
do mid <-- (low+high)/2
if v=A[mid]
return mid
if v>A[mid]
low<-- mid + 1
else high <-- mid - 1
return Null

Example:-

low=0     high=6
mid = 0+6/2  =3
v=14
A[mid]=26
high = mid -1   = 3-1    = 2
low=0    mid = 0 + 2/2   =1
v = A[mid] , A[1]=14

No comments