20. Linear Search and Binary Search-1.pdf

Linear programming and binary

1. scalescale
Search Algorithms
Technical Writing(CS1305) Assignment
Aditya Kumar
20142028
MNNIT Allahabad
August 2015
Aditya Kumar 20142028 Search Algorithms

2. scalescale
Introduction
In computer science, a search algorithm is an algorithm
for finding an item with specified properties among a
collection of items which are coded into a computer
program.
The program then looks for clues to give us back exactly
what we want.
Aditya Kumar 20142028 Search Algorithms

3. scalescale
Introduction
In computer science, a search algorithm is an algorithm
for finding an item with specified properties among a
collection of items which are coded into a computer
program.
The program then looks for clues to give us back exactly
what we want.
We are going to cover two search algoritms in this
presentation: linear and binary.
Aditya Kumar 20142028 Search Algorithms

4. scalescale
Linear Search
Linear search is a method for finding a particular value in
a list that checks each element in sequence until the
desired element is found or the list is exhausted
Aditya Kumar 20142028 Search Algorithms

5. scalescale
Linear Search
Linear search is a method for finding a particular value in
a list that checks each element in sequence until the
desired element is found or the list is exhausted
It is the simplest search algorithm
A special case of brute-force search
Average time complexity:O(n)
Aditya Kumar 20142028 Search Algorithms

6. scalescale
Linear Search
continued
Figure:Graphical illustration of linear search
Aditya Kumar 20142028 Search Algorithms

7. scalescale
Linear Search
Pseudocode
Using Iteration
Require:lista, size of listn, desired itemx
fori=0ton-1do
ifa[i]=xthen
returni
end if
i=i+1
end for
ifi=nthen
return false
end if
Aditya Kumar 20142028 Search Algorithms

8. scalescale
Linear Search
Advantages and Disadvantages
Advantages
Easiest to understand and implement
No sorting required
Suitable for small list sizes
Aditya Kumar 20142028 Search Algorithms

9. scalescale
Linear Search
Advantages and Disadvantages
Advantages
Easiest to understand and implement
No sorting required
Suitable for small list sizes
Disadvantages
Time inefficient as compared to other algorithms
Not suitable for large-sized lists
Aditya Kumar 20142028 Search Algorithms

10. scalescale
Binary Search
Binary search algorithm finds the position of a target
value within a sorted array
Aditya Kumar 20142028 Search Algorithms

11. scalescale
Binary Search
Binary search algorithm finds the position of a target
value within a sorted array
It can be classified as a divide-and-conquer search
algorithm
Average time complexity: O(logn)
Aditya Kumar 20142028 Search Algorithms

12. scalescale
Binary Search
Overview
The algorithm begins by comparing the target value to
the value of the middle element of the sorted array
Aditya Kumar 20142028 Search Algorithms

13. scalescale
Binary Search
Overview
The algorithm begins by comparing the target value to
the value of the middle element of the sorted array
If they are equal the middle position is returned and the
search is finished
Aditya Kumar 20142028 Search Algorithms

14. scalescale
Binary Search
Overview
The algorithm begins by comparing the target value to
the value of the middle element of the sorted array
If they are equal the middle position is returned and the
search is finished
If the target value is less than the middle element’s value,
then the search continues on the lower half of the array;
or if the target value is greater than the middle element’s
value, then the search continues on the upper half of the
array
Aditya Kumar 20142028 Search Algorithms

15. scalescale
Binary Search
Overview
The algorithm begins by comparing the target value to
the value of the middle element of the sorted array
If they are equal the middle position is returned and the
search is finished
If the target value is less than the middle element’s value,
then the search continues on the lower half of the array;
or if the target value is greater than the middle element’s
value, then the search continues on the upper half of the
array
This process continues, eliminating half of the elements
until the value is found or the array is exhausted
Aditya Kumar 20142028 Search Algorithms

16. scalescale
Binary Search
continued
Figure:Graphical illustration of binary search
Aditya Kumar 20142028 Search Algorithms

17. scalescale
Binary Search
Pseudocode (using iteration)
BinarySearch(list[], min, max, key)
whilemin≤maxdo
mid = (max+min) / 2
iflist[mid]>keythen
max = mid-1
else iflist[mid]<keythen
min = mid+1
else
returnmid
end if
end while
return false
Aditya Kumar 20142028 Search Algorithms

18. scalescale
Binary Search
Performance
With each test that fails to find a match, the search is
continued with one or other of the two sub-intervals, each
at most half the size
Aditya Kumar 20142028 Search Algorithms

19. scalescale
Binary Search
Performance
With each test that fails to find a match, the search is
continued with one or other of the two sub-intervals, each
at most half the size
If the original number of items isNthen after the first
iteration there will be at mostN=2 items remaining, then
at mostN=4 items, and so on
Aditya Kumar 20142028 Search Algorithms

20. scalescale
Binary Search
Performance
With each test that fails to find a match, the search is
continued with one or other of the two sub-intervals, each
at most half the size
If the original number of items isNthen after the first
iteration there will be at mostN=2 items remaining, then
at mostN=4 items, and so on
In the worst case, when the value is not in the list, the
algorithm must continue iterating until the list is empty;
this take at mostfloor(log
2N+ 1) iterations, where
floor()rounds down its argument to an integer
Aditya Kumar 20142028 Search Algorithms

21. scalescale
Binary Search
Performance
With each test that fails to find a match, the search is
continued with one or other of the two sub-intervals, each
at most half the size
If the original number of items isNthen after the first
iteration there will be at mostN=2 items remaining, then
at mostN=4 items, and so on
In the worst case, when the value is not in the list, the
algorithm must continue iterating until the list is empty;
this take at mostfloor(log
2N+ 1) iterations, where
floor()rounds down its argument to an integer
Thus binary search runs in logarithmic time
Aditya Kumar 20142028 Search Algorithms

22. scalescale
Binary Search
Advantages and Disadvantages
Advantages
Excellent time efficiency
Suitable for large list sizes
Aditya Kumar 20142028 Search Algorithms

23. scalescale
Binary Search
Advantages and Disadvantages
Advantages
Excellent time efficiency
Suitable for large list sizes
Disadvantages
Can only be implemented on a sorted array
Not suitable for small sizes, where linear search would be
faster, as sorting takes up a considerable amount of time
Aditya Kumar 20142028 Search Algorithms