Scribd
Upload
1 views

Lecture 1.2_correctness_binary_search

The document provides an overview of the binary search algorithm, including its implementation, input/output definitions, and proof of correctness through loop invariants. It discusses the time complexity of the algorithm, detailing both worst-case and best-case scenarios, concluding that the worst-case time complexity is O(log n) and the best-case is O(1). The author, Neelima Gupta, presents this material as part of a course on the design and analysis of algorithms.

Uploaded by

rdxsingh01
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
1 views

Lecture 1.2_correctness_binary_search

The document provides an overview of the binary search algorithm, including its implementation, input/output definitions, and proof of correctness through loop invariants. It discusses the time complexity of the algorithm, detailing both worst-case and best-case scenarios, concluding that the worst-case time complexity is O(log n) and the best-case is O(1). The author, Neelima Gupta, presents this material as part of a course on the design and analysis of algorithms.

Uploaded by

rdxsingh01
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/ 19

MCSC 101: Design and Analysis of Algorithms

Neelima Gupta

ngupta@cs.du.ac.in

January 4, 2021

1/12
Binary Search
Binary-Search(A[], n, key )
left 1, right n
while left  right do
mid (left+right)/2
if (A[mid]=key) then
return mid
end
if (A[mid] < key) then
left mid+1
end
else
right mid-1
end
end
return 0

2/12
Defining the I/O of Binary Search

I Input : Given an array L containing n items (n 0) ordered


such that A[1]  A[2]  A[3]  . . .  A[n] and given x
I Output : The binary search algorithm terminates with
index mid = an occurrence of x in A, if found and,
index mid= 0 otherwise.

Binary search can only be applied if the array to be searched is


already sorted

3/12
4/12
5/12
Proof of correctness: The Loop Invariant

Let r be the maximum number of times the loop starting from line
3 runs. For 1  k  r , let fk and lk be the values of first and last
respectively when the control reaches the while statement for the
k th time.
I Loop Invariant: For 1  k  r , H(k): when the control
reaches the while statement for the k th time A[i] 6= x for
every i < fk and for every i > lk .
I We will prove the loop invariant by induction.
I Base Case: k = 1. fk = 1 and lk = n. Hence the claim is
vacuously true.

6/12
Inductive Step: Suppose H(k) is true. We will prove that H(k + 1)
is true. In the k th iteration, we have three possibilities:

I Case 1: x = A[mk ] . . . .not possible else we wouldn’t enter the


loop (k + 1)th time.

7/12
I Case 2. x < A[mk ].

Since the array is sorted, we have


x < A[mk ]  A[i] 8i = mk + 1 . . . lk .
i.e. x 6= A[i] 8i = mk . . . lk .

8/12
I Case 3. x > A[mk ] .

Since the array is sorted, we have


x > A[mk ] A[i] 8i = fk . . . mk 1.
i.e. x 6= A[i] 8i = fk . . . mk .

9/12
Correctness of the algorithm assuming the loop invariant

Suppose the test condition is executed t times.


I Case 1: ft  lt . We exit from the loop because A[mt ] = x.
Thus, index mid is a position of occurrence of x as index mid
= mt
I Case 2: If ft > lt , we exit the while statement and return 0.
We will next argue that the element is not present in the array
in this case:
By loop invariant hypothesis, A[i] 6= x for i < ft and for
i > lt . the claim follows as ft > lt .
Hence assuming that the statement H(k) is correct the algorithm
works correctly.

10/12
Correctness of the algorithm assuming the loop invariant

By loop invariant hypothesis, A[i] 6= x for i < ft and for i > lt . the
claim follows as ft > lt .

11/12
Time Complexity

Let W (n) be the number of comparisons performed by the binary


search algorithm in worst case. Then,

12/12
Time Complexity

Let W (n) be the number of comparisons performed by the binary


search algorithm in worst case. Then,
W (n) =?

12/12
Time Complexity

Let W (n) be the number of comparisons performed by the binary


search algorithm in worst case. Then,
W (n) =?
W (n) = W (n/2)+?

12/12
Time Complexity

Let W (n) be the number of comparisons performed by the binary


search algorithm in worst case. Then,
W (n) =?
W (n) = W (n/2)+?
W (n) = W (n/2) + 2

12/12
Time Complexity

Let W (n) be the number of comparisons performed by the binary


search algorithm in worst case. Then,
W (n) =?
W (n) = W (n/2)+?
W (n) = W (n/2) + 2
W (n) =?

12/12
Time Complexity

Let W (n) be the number of comparisons performed by the binary


search algorithm in worst case. Then,
W (n) =?
W (n) = W (n/2)+?
W (n) = W (n/2) + 2
W (n) =? W (n) = log n
Let B(n) be the number of comparisons performed by the binary
search algorithm in best case. Then,

12/12
Time Complexity

Let W (n) be the number of comparisons performed by the binary


search algorithm in worst case. Then,
W (n) =?
W (n) = W (n/2)+?
W (n) = W (n/2) + 2
W (n) =? W (n) = log n
Let B(n) be the number of comparisons performed by the binary
search algorithm in best case. Then,
B(n) =?

12/12
Time Complexity

Let W (n) be the number of comparisons performed by the binary


search algorithm in worst case. Then,
W (n) =?
W (n) = W (n/2)+?
W (n) = W (n/2) + 2
W (n) =? W (n) = log n
Let B(n) be the number of comparisons performed by the binary
search algorithm in best case. Then,
B(n) =?
B(n) = 1

12/12

You might also like