Question

Implement the function def findChange(lst01). This function is given lst01, a list of integers containing a sequence of 0s followed by a sequence of 1s. When called, it returns the index of the first 1 in lst01. For example, if lst01 is a list containing [0, 0, 0, 0, 0, 1, 1, 1], calling findChange(lst01) will return 5. Note: Pay attention to the running time of your function. If lst01 is a list of size �, an efficient implementation would run in logarithmic time (that is Θ(���'(�))).

Answer 1

Solution and Explanation:

The following is the function which will implement the required change as asked in the question.

def findChange(lst01):

left = 0

right = len(lst)-1

while (left <= right):

   middle = (left + right)// 2

   if (lst01[middle] == 1 and (middle == 0 or lst01[middle - 1] == 0)):

     return middle

   elif (lst01[middle] == 1):

     right = middle - 1

   else:  

     left = middle + 1

return -1;

lst = [0, 0, 0, 0, 0, 1,1]  

print(findChange(lst))

Please see the attched file.