6/25/2019
Design & Analysis of Algorithm
Department of Computer Science &
Software Engineering
University of Swat
CS Course : Design and Analysis of Algorithm
Course Instructor : Muzammil Khan
Chapter 8
Searching Algorithms
1
6/25/2019
Searching
In computer science, a search algorithm is
An algorithm for finding an item with specified properties
among a collection of items
For Example
Linear Search
Binary Search
Etc…
Design & Analysis of Algorithms
Linear Search Algorithm
Design & Analysis of Algorithms
2
6/25/2019
Linear Search
Linear Search
Is also known as Sequential Search
Mechanism
Search starts at the first element in the list and
Continues until either
The item is found in the list or
The entire list is searched
Feasible for small and unsorted list
Order of the list does not matter
Will have same effect (all orders)
Design & Analysis of Algorithms
Linear Search Algorithm
ARRAY-SEARCH(Arr, n, key)
1. for (i=1; i<=n; i++)
2. if A[i]=key
3. return i (the value is found)
4. return -1 (the value is not found)
Design & Analysis of Algorithms
3
6/25/2019
Linear Search – Average and Worst Case
Worst Case running time is
Array as data structure
Θ (n)
Linked list as data structure
Θ (n)
Average Case running time is
Search in an array can be computed by assuming a key has
equal probability of being in any position i.e. 1/n
Then T(n) = 1c*1/n+2c*1/n+….+nc*1/n
= c/n(1+2+3+…+n)=cn(n+1)/2n =θ(n)
Design & Analysis of Algorithms
Randomized Linear Search Algorithm
Design & Analysis of Algorithms
4
6/25/2019
Randomized Linear Search
Is a modified form of linear search method
Is used on Presorted array
Proceeds as follows
Step # 1 : Starting with 1st element of the array, the array is scanned
using iterative loops
Step # 2 : In each loop a random number is generated in the range
1-n (n is size of the array)
Step # 3 : If the random number is greater than current value of
loop index & the cell accessed by random value is less than or
equal to the key, then
Loop index is incremented to the random value, otherwise
The loop index is incremented by 1
Step # 4 : Steps 2 & 3 are repeated until loop terminated
Design & Analysis of Algorithms
Randomized Linear Search Algorithm
Running time of Randomized linear search algorithm is θ(√n)
Design & Analysis of Algorithms
5
6/25/2019
Binary Search Algorithm
Design & Analysis of Algorithms
Binary Search
Feasible for large and sorted list/array
Mechanism
Located the middle of the sorted list
Compare the middle value with the search key
If the values are equal – Done !
Otherwise: Eliminate one half of the list after comparison
with the key
Decide; which half of the list contains the key
Repeat the above steps on selected half of the list
The search continues until the key is matched or no element
remain to be searched
Design & Analysis of Algorithms
6
6/25/2019
Binary Search (Cont...)
An array of one billion elements takes
Maximum of 30 comparisons
Because of binary search techniques
The bigger the array the better a binary search technique
As compared to a linear search
Design & Analysis of Algorithms
Binary Search Working
Design & Analysis of Algorithms
7
6/25/2019
Binary Search Working (Cont...)
Design & Analysis of Algorithms
Binary Search Algorithm
Design & Analysis of Algorithms
8
6/25/2019
Analysis of Binary Search Algorithm
The recurrence of Binary search algorithm
By solving recurrence the Running time of Binary Search
algorithm
Θ (lg n)
Design & Analysis of Algorithms
Analysis of Binary Search Algorithm (Cont...)
Design & Analysis of Algorithms
9
6/25/2019
Analysis of Binary Search Algorithm (Cont...)
Design & Analysis of Algorithms
Analysis of Binary Search Algorithm (Cont...)
Design & Analysis of Algorithms
10
6/25/2019
MS Course
Hashing
Design & Analysis of Algorithms
End of Chapter
You May Have Quiz Next Week
Design & Analysis of Algorithms
11
