Question

Write a modification of the recursive binary search algorithm that always returns the smallest index whose element matches the search element. Your algorithm should still guarantee logarithmic runtime. Give a brief discussion of the best- and worst-case runtimes for this new algorithm as they compare to the original.

NOTE: You do not have to re-write the entire algorithm. You just need to indicate any changes you would make and show the pseudocode for any portions that are changed.

Example: Given the array [0, 0, 1, 1, 1, 2, 2, 3] and the search element 1, the algorithm should return 2.

Answer 1

Let algorithm be called modifiedBinarySearch(a, i , j , k)

here , 'a' is input array, 'i' is first index of array , 'j' is last index of array and 'k' is search element .

here n = j-i+1

C style pseudoCode:-

int modifiedBinarySearch(a, i , j , k) // it takes time = T(n)

{

if(i==j)// it takes c1 time

{

if (a[i]==k)// it takes c2 time

return i

else

return -1 // means no 'k' element.

}

else

{

m = floor((i+j)/2)// it takes c3 time

if(a[m]==k)// it takes c4 time

{

if(a[m-1]!=k)/* it takes c5 time, this is change in original binary search algorithm . if you element this then rest is binary search */

return m

}

else if(a[m]>=k)

return modifiedBinarySearch(a, i , m-1 , k) // it takes T(n/2)

else

return modifiedBinarySearch(a, m+1 , j , k) // it takes T(n/2)

}

}

Time complexity analysis:-

In best case :-

In best case we will find our required index first attempt itself.so , T(n) = c1 + c3+ c4 + c5

let c1 + c3+ c4 + c5 = c, after all sum of constants is a constant

so , T(n) = c = O(1)

now , we know that in binary search only one statement which takes c5 time is not available.

so , time taken by binary search T(n) = c1 + c4 + c5 = O(1)

so , we can see that order of growth of both algorithms(modifiedBinarySearch and BinarySearch) are same.

In Worst case:-

In worst case , the recursive calls are executed.

so , recursive relation that appears is

T(n) = T(n/2) + c , if n >1

= O(1) , n=1

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

solving above using subsitution we get

T(n) = T(n/2²) + c + c

= T(n/2³) + c+ c+ c

continuing like this 'd' times we get

= T(n/2^d) + c+ c+...d times

it will stop when n/2^d =1 so , d = log₂n

= T(1) + c.log₂n

= O(1) + log₂n = O(log₂n)

In Binary search same recurrence relation appears so , time taken by binary search in worst case = O(log₂n)

so , we can see that order of growth of both algorithms(modifiedBinarySearch and BinarySearch) are same even in worst case.

if we apply algorithm then on given example

modifiedBinarySearch(a, 0 , 7 , 1)

m = 3

a[m] = 1 is true a[m-1]!=1 is not true so , another recursive call occurs

since a[m]==k so ,

modifiedBinarySearch(a, 0 , 2 , 1)

m = 1

a[m] = 1 is not true therefore , another recursive call occurs.

since a[m] < 1 so ,

modifiedBinarySearch(a, 2,2,1)

so , it now returns 2 as answer .