Simplify Complexities

Problem

Count number of 1s in a sorted array.

e.g. [1,1,1,1,0,0,0,0,0,0]

Code

def countOneBS(row, start, end):
        if row[start] == 0:
            return 0
        
        if row[end] == 1:
            return end - start + 1
        
        # The mid is dependent on the index of start
        mid = start + (end - start) // 2
        # print("mid=", mid, "start=", start, "end=", end)
        return countOneBS(row, start, mid) + countOneBS(row, mid + 1, end)
    
l = [1,1,1,0,0,0]

print(countOneBS(l, 0, len(l) - 1))

Reference

• https://www.techiedelight.com/find-number-1s-sorted-binary-array/