Question

You are given an array of length n that is filled with two symbols (say 0 and 1); all m copies of one symbol appear first, at the beginning of the array, followed by all n − m copies of the other symbol. You are to find the index of the first copy of the second symbol in time O(logm).

include: code,  proof of correctness, and runtime analysis  

Answer 1

For this i have used the binary search feature to find the first index of second symbol

// Code

def code(arr,symbol1,symbol2):
n=len(arr)
left=0
right=n-1
while(left<right):
mid=int((left+right)/2)
if arr[mid]==symbol1:
left=mid+1
else:
right=mid
return right+1

arr=[0,0,0,0,0,1,1,1,1,1]
print("first index of second symbol :",code(arr,arr[0],arr[len(arr)-1]))

arr=[0,0,0,0,0,1]
print("first index of second symbol :",code(arr,arr[0],arr[len(arr)-1]))

arr=[0,0,1,1,1,1,1]
print("first index of second symbol :",code(arr,arr[0],arr[len(arr)-1]))

//OUTPUT

• input

first index of second symbol : 6                                                                                                                                             

first index of second symbol : 6                                                                                                                                             

first index of second symbol : 3                                                                                                                                             

                                                                                                                                                                             

                                                                                                                                                                             

...Program finished with exit code 0                                                                                                                                         

Press ENTER to exit console.              

Code is being verified for various inputs

// RUNTIME ANALYSIS

at iteration 1 : length of array =n

at iteration 2 : length of array =n/2

at iteration 3 : length of array =n/4

at iteration 4 : length of array =n/8

at iteration k : length of array =

Applying log function on both sides:

 log2 (n) = log2 (2k)
 log2 (n) = k log2 (2)
As (loga (a) = 1)

Therefore,

 k = log2 (n)

HENCE THE COMPLEXITY IS : O(log₂ (n))

//CODE

//OUTPUT