Scribd
Upload
6 views

Chapter # 8 Searching Algorithms

Uploaded by

MURTAZA
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
6 views

Chapter # 8 Searching Algorithms

Uploaded by

MURTAZA
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 11

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

You might also like