Scribd
Upload
587 views21 pages

Analysis & Design of Algorithms: Binary Search

This document describes the binary search algorithm. It begins by stating that binary search is one of the fastest searching algorithms used to find an element in a sorted linear list. It works by dividing the search space in half at each step by comparing the target value to the middle element of the list. This process continues recursively on either half of the list until the target is found or the list is exhausted. The best case running time is O(1) if the target is the middle element, and the average and worst case is O(log n) as the list is divided by half at each step.

Uploaded by

Krisha Davda
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
587 views21 pages

Analysis & Design of Algorithms: Binary Search

This document describes the binary search algorithm. It begins by stating that binary search is one of the fastest searching algorithms used to find an element in a sorted linear list. It works by dividing the search space in half at each step by comparing the target value to the middle element of the list. This process continues recursively on either half of the list until the target is found or the list is exhausted. The best case running time is O(1) if the target is the middle element, and the average and worst case is O(log n) as the list is divided by half at each step.

Uploaded by

Krisha Davda
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

Analysis & Design of Algorithms

Binary Search • Prepared by:-

Sagar Virani

Assistant Professor

Computer Engineering
Department

VVP Engineering College


Binary Search
• Binary Search is one of the fastest searching algorithms.
• It is used for finding the location of an element in a linear list.
• It works on the principle of divide and conquer technique.
• Binary Search Algorithm can be applied only on sorted list.
• So, the elements must be arranged in-
• Either ascending order if the elements are numbers.
• Or alphabetical / dictionary / lexicographical order if the
elements are strings.
• To apply binary search on an unsorted list,
• First, sort the list using some sorting technique.
• Then, use binary search algorithm.
Binary Search
• Binary Search Algorithm searches an element by comparing it with the
middle most element of the list.
• If the element being searched is,
Case-01
• Found to be the middle most element, its index is returned.
Case-02
• Found to be greater than the middle most element, then its search is further
continued in the right sub array of the middle most element.
Case-03
• Found to be smaller than the middle most element, then its search is further
continued in the left sub array of the middle most element.
• This iteration keeps on repeating on the sub arrays until the desired element is
found or size of the sub array reduces to zero.
Binary Search
List

20 12 65 8 10 16 43 35 23 88 2 56 41 27 67 57
Binary Search
Sorted List

2 8 10 12 16 20 23 27 35 41 43 56 57 65 67 88
Key = 41
Binary Search
Element to be found
1 16

2 8 10 12 16 20 23 27 35 41 43 56 57 65 67 88

low high

1 16 41
BINARY-SEARCH (A, low, high, key)
Key = 41
Binary Search
1 8 16

2 8 10 12 16 20 23 27 35 41 43 56 57 65 67 88

low mid high

1 16 41
BINARY-SEARCH (A, low, high, key)
mid = (low + high) / 2 8
Key = 41
Binary Search
1 8 16

2 8 10 12 16 20 23 27 35 41 43 56 57 65 67 88

low mid high

1 16 41
BINARY-SEARCH (A, low, high, key)
mid = (low + high) / 2 8
27 41
if A [ mid == key ]
return mid
27 41
else if A[ mid ] > key
return BINARY-SEARCH(A, low, mid – 1, key)
else 9 16
return BINARY-SEARCH(A, mid + 1, high, key)
Key = 41
Binary Search
8 9 16

2 8 10 12 16 20 23 27 35 41 43 56 57 65 67 88

mid low high

9 16 41
BINARY-SEARCH (A, low, high, key)
mid = (low + high) / 2
if A [ mid == key ]
return mid
else if A[ mid ] > key
return BINARY-SEARCH(A, low, mid – 1, key)
else
return BINARY-SEARCH(A, mid + 1, high, key)
Key = 41
Binary Search
9 12 16

2 8 10 12 16 20 23 27 35 41 43 56 57 65 67 88

low mid high

9 16 41
BINARY-SEARCH (A, low, high, key)
mid = (low + high) / 2 12
56 41
if A [ mid == key ]
return mid
56 41
else if A[ mid ] > key
9 11
return BINARY-SEARCH(A, low, mid – 1, key)
else
return BINARY-SEARCH(A, mid + 1, high, key)
Key = 41
Binary Search
9 11 12

2 8 10 12 16 20 23 27 35 41 43 56 57 65 67 88

low high mid

9 11 41
BINARY-SEARCH (A, low, high, key)
mid = (low + high) / 2
if A [ mid == key ]
return mid
else if A[ mid ] > key
return BINARY-SEARCH(A, low, mid – 1, key)
else
return BINARY-SEARCH(A, mid + 1, high, key)
Key = 41
Binary Search
9 10 11

2 8 10 12 16 20 23 27 35 41 43 56 57 65 67 88

low mid high

9 12 41
BINARY-SEARCH (A, low, high, key)
mid = (low + high) / 2 10
if A [ mid == key ]
return mid
else if A[ mid ] > key
return BINARY-SEARCH(A, low, mid – 1, key)
else
return BINARY-SEARCH(A, mid + 1, high, key)
Key = 41
Binary Search
9 10 11

2 8 10 12 16 20 23 27 35 41 43 56 57 65 67 88

low mid high


Element found!!!
9 12 41
BINARY-SEARCH (A, low, high, key)
mid = (low + high) / 2 10
41 41
if A [ mid == key ]
return mid
else if A[ mid ] > key
return BINARY-SEARCH(A, low, mid – 1, key)
else
return BINARY-SEARCH(A, mid + 1, high, key)
Binary Search
2 8 10 12 16 20 23 27 35 41 43 56 57 65 67 88

Time Analysis:
BINARY-SEARCH (A, low, high, key) Best Case:
mid = (low + high) / 2 • Key is always the middle element in the list
if A [ mid == key ] irrespective to the size of the list.
return mid
else if A[ mid ] > key
return BINARY-SEARCH(A, low, mid – 1, key)
else
return BINARY-SEARCH(A, mid + 1, high, key)
Key = 27
Binary Search
2 8 10 12 16 20 23 27 35 41 43 56 57 65 67 88

Time Analysis:
BINARY-SEARCH (A, low, high, key) Best Case:
mid = (low + high) / 2 • Key is always the middle element in the list
if A [ mid == key ] irrespective to the size of the list.
return mid • Running time of BINARY-SEARCH = Ω(1)
else if A[ mid ] > key
return BINARY-SEARCH(A, low, mid – 1, key)
else
return BINARY-SEARCH(A, mid + 1, high, key)
Key = 37 / 41
Binary Search
2 8 10 12 16 20 23 27 35 41 43 56 57 65 67 88

Time Analysis:
BINARY-SEARCH (A, low, high, key) Worst / Average Case:
mid = (low + high) / 2 • For worst case, key element is not present in
if A [ mid == key ] the list or the last element to be found in the
return mid list.
else if A[ mid ] > key • Running time of BINARY-SEARCH = ?
return BINARY-SEARCH(A, low, mid – 1, key)
else
return BINARY-SEARCH(A, mid + 1, high, key)
Worst / Average case
• Let the iteration in Binary Search terminates after k iterations (in average case
the value of k will be half then it is in worst case).
• At iteration 1 the length of the list is n.
• At iteration 2 the length of the list is n/2.
• At iteration 3 the length of the list is n/22.
.
.
• At iteration k the length of the list is n/2k.
• After k division the length of the array becomes 1.
• Length of the array:
n/2k = 1
=> 2k = n.
=> k = = lg n
• Running time of BINARY-SEARCH = O(lg n).
Advantages
• Simple implementation.
• It eliminates half of the list from further searching by using the result
of each comparison.
• It indicates whether the element being searched is before or after
the current position in the list.
• This information is used to narrow the search.
• For large lists of data, it works significantly better than linear
search.
Disadvantages
• Can be applied only on sorted list only.
• It employs recursive approach which requires more stack space.
• Programming binary search algorithm is error prone and difficult.
• The interaction of binary search with memory hierarchy i.e. caching is
poor(because of its random-access nature).
• As the n um be r of elements increases the performance of the
program w ou l d be slow.
Pseudo code for Binary Search
Algorithm
BINARY-SEARCH (A, low, high, key)
{
mid = (low + high) / 2
if A [ mid == key ]
return mid
else if A[ mid ] > key
return BINARY-SEARCH(A, low, mid – 1, key)
else
return BINARY-SEARCH(A, mid + 1, high, key)
}
Any Questions?

You might also like