Question

algorithm binarySearch

input

bottom, top: a number

   a: array a[0] to a[n-1] of numbers

   x: a number

output

result:

true if x in a

false otherwise

Sideeffect NA

Plan

if (top < bottom) result := false

else

// get the middle of the array (refining)

middle := (top - bottom)/2 + bottom (refining by +1 or -1 or integer division …)

// example what is midpoint between 6 and 8

// (8-6)/2 = 1 we need to add 6 to get the “absolute middle point”

if (x is a[middle])

result := true

else

if x is larger than middle element

// find if x is in the second half

result := binarySearch(middle+1, top,a,x)

Else

// find if x is in the first half

result := binarySearch(bottom, middle-1, a, x)

Following the binary search algorithm (final version) in the lecture notes, write a recurrence relation for the running time T(n), where n is the input size, of the algorithm. 2) Give the best asymptotic upper bound for the running time of the algorithm.

Answer 1

bottom, top: a number

   a: array a[0] to a[n-1] of numbers

   x: a number

output

result:

true if x in a

false otherwise

Sideeffect NA

Plan

if (top < bottom) result := false

else

// get the middle of the array (refining)

middle := (top - bottom)/2 + bottom (refining by +1 or -1 or integer division …) //O(1)

// example what is midpoint between 6 and 8

// (8-6)/2 = 1 we need to add 6 to get the “absolute middle point”

if (x is a[middle]) //O(1)

result := true

else

if x is larger than middle element

// find if x is in the second half

result := binarySearch(middle+1, top,a,x) //T(n/2)

Else

// find if x is in the first half

result := binarySearch(bottom, middle-1, a, x) //T(n/2)

1. T(n)= { c if(i>=j) }

{ T(n/2)+c if(i<j) }

Derivation->

T(n)=T(n/2) + 1

T(n/2)=T(n/4) + 1 ……[ T(n/4)= T(n/2^2) ]

T(n/4)=T(n/8) + 1 ……[ T(n/8)= T(n/2^3) ]

.**

**

**

.kth step=> T(n/2^k-1)=T(n/2^k) + 1*(k times)

Adding all the equations we get, T(n) = T(n/2^k) + k times 1 _____eq(final)

n/2^k= 1

n=2^k

log n=k [taken log(base 2) on both sides ]

Put k= log n in eq(final)

T(n) = T(1) + log n

T(n) = 1 + log n [we know that T(1) = 1 , because it’s a base condition as we are left with only one element in the array and that is the element to be searched so we return 1]

T(n) = O(log n) [taking dominant polynomial, which is n here)

2. Time Complexity:

• Best Case: O(1)
• Average Case: O(logn)
• Worst Case: T(n)=T(n/2)+c, By using master Theorem O(logn)

This is how we got “log n” time complexity for binary search. Hope this might help :) .