CSEN3001 - Design and Analysis of Algorithm

RAVI KANTH SATPATI

1
Searching Algorithms:

Searching:
 Process of finding a particular item in a collection of items.

 A search typically answers either Found or Not Found.

Algorithms: They are two types of searching algorithms.

1) Linear Search
- small arrays
- unsorted arrays

2) Binary Search
- large arrays
- sorted arrays

2
1. Linear Search Algorithm

• a linear search or sequential search is a method for finding an

List 5 77 8 33 9 2
a[1] a[2] a[3] a[4] a[5] a[6]
Search Element=9
i=1 i=2 i=3 i=4 i=5
Found Stop

3
1. Linear Search Algorithm
Algorithm( a, n, x)
// a is an array , n is size , x is search element
{
int i;
for i:=1 to n do
{
if(a[i]==x)
return i;
}
}
TC= Best case O(1)
Average Case O(n/2)
Worst Case O(n)
4
2. Binary Search Algorithm Using DandC Technique:
 Binary Search is a fast search algorithm with run-time complexity Ο(log n).
 Binary search algorithm works only on the sorted list.
Procedure: Binary Search Algorithm follows divide and conquer approach, in which, the list is divided
into two halves.(Mid Point).
• Binary search begins by comparing a search item with the middle element of the list.
Three Possibilities:
1) If the search item is equal to middle element , then its position in the array is returned.
2) If the search item is less than the middle element then
the search continues in the lower half of the array(i.e LoweBound to Mid-1).
3) If the search item is greater than the middle element then
the search continues in the upper half of the array(i.e Mid+1 to UpperBound).
By doing this,
• In each iteration the algorithm eliminates the half of the array in which the search item cannot lie .
5
2. Binary Search Algorithm-Numerical Explaination

Binary search. Given a Search value and sorted array a[lb : Ub],
find index i such that a[i] = Search value, or report that no such index exists.
Ex. Binary search for search value 33 and below sorted array

6 13 14 25 33 43 51 53 64 72 84 93 95 96 97
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

lb ub

6
2. Binary Search Algorithm-Numerical Explaination
Ex. Consider the following list and search the value 33
6 13 14 25 33 43 51 53 64 72 84 93 95 96 97
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

lb mid ub
Step 1: Find Mid lb=1 ,ub=15 , mid = (lb+ub)/2=(1+15)/2=16/2 = 8 a[mid] = a[8] = 53
Step 2: Check Search value and a[mid]
is 33=53 no
is 33 < 53 yes , so the search value 33 may present in left sub array.
the next search will use the lower half of the array(left sub array).
So lower half is from lb to mid-1 i.e lb=1 to ub=mid-1
6 13 14 25 33 43 51
1 2 3 4 5 6 7

lb Ub=mid-1
Repeat the same procedure for the above
2. Binary Search Algorithm-Numerical Explaination
Repeat the same procedure: Search value is : 33

6 13 14 25 33 43 51 53 64 72 84 93 95 96 97
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

lb mid ub
Step 1: lb=1 ,ub=7 , mid = (lb+ub)/2=(1+7)/2=8/2 = 4 a[mid] = a[4] = 25
Step 2: check search value and a[mid]
33 > 25 so the search value 33 may present in right sub array.
the next search will use the upper half of the array(right sub array).
So upper half is from mid+1 to ub i.e lb=mid+1 to ub=7
6 13 14 25 33 43 51 53 64 72 84 93 95 96 97
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

lb ub

Repeat the same procedure 8

6 13 14 25 33 43 51 53 64 72 84 93 95 96 97
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

lb mid ub
Step 1: lb=5 ,ub=7 , mid = (lb+ub)/2=(5+7)/2=12/2 = 6 a[mid] = a[6] = 43
Step 2: check search value and a[mid]
33 < 43 so the search value 33 may present in left sub array.
the next search will use the lower half of the array(left sub array).
So lower half is from lb to mid-1 i.e lb=5 to ub=mid-1=>6-1=>5
6 13 14 25 33 43 51 53 64 72 84 93 95 96 97
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

lb
ub Repeat the same procedure
9
2. Binary Search Algorithm-Numerical Explaination
Repeat the same procedure: Search value is: 33
6 13 14 25 33 43 51 53 64 72 84 93 95 96 97
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

lb, ub

Step 1: lb=5 ,ub=5 , Now the problem is small Only One Element.
So check search value and that one element i.e a[lb] or a[ub] ( lb==ub)
33 = 33 so the search value 33 is present at 5.
Success!

6 13 14 25 33 43 51 53 64 72 84 93 95 96 97
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

10
2. Binary Search : Algorithm
Algorithm: AlgorithmBinsrch( a, lb, ub, X)
// Given a sorted array a[lb:ub]
// X is search item , if X is present such that
X=a[i] // return i(index) , else return 0. mid=(lb+ub)/2;
if(X=a[mid]) then
return mid;
else if(X<a[mid]) then
return Binsrch(a, lb, mid-1, X);
else
return Binsrch(a, mid+1, ub, X);

11
2. Binary Search : Algorithm(conti..)
Algorithm: AlgorithmBinsrch( a, lb, ub, X)
// Given a sorted array a[lb:ub]
// X is search item , if X is present such that else {
X=a[i] // return i(index) , else return 0. mid=(lb+ub)/2;
{ if(X=a[mid]) then
if (lb=ub) then //if Small(P) return mid;
{ else if(X<a[mid]) then
if(X=a[lb]) then return Binsrch(a, lb, mid-1, X);
return lb; else
else return Binsrch(a, mid+1, ub, X);
return 0; }
} }
12
13
14
THANK YOU

15
59