Count 1 's in a sorted binary array | Returns counts of 1 's in arr[low..high]. The array is assumed to be sorted in non-increasing order ; get the middle index ; check if the element at middle index is last 1 ; If element is not last 1 , recur for right side ; else recur for left side ; Driver Code
def countOnes ( arr , low , high ) : NEW_LINE INDENT if high >= low : NEW_LINE INDENT mid = low + ( high - low ) // 2 NEW_LINE if ( ( mid == high or arr [ mid + 1 ] == 0 ) and ( arr [ mid ] == 1 ) ) : NEW_LINE INDENT return mid + 1 NEW_LINE DEDENT if arr [ mid ] == 1 : NEW_LINE INDENT return countOnes ( arr , ( mid + 1 ) , high ) NEW_LINE DEDENT return countOnes ( arr , low , mid - 1 ) NEW_LINE DEDENT return 0 NEW_LINE DEDENT arr = [ 1 , 1 , 1 , 1 , 0 , 0 , 0 ] NEW_LINE print ( " Count ▁ of ▁ 1 ' s ▁ in ▁ given ▁ array ▁ is " , countOnes ( arr , 0 , len ( arr ) - 1 ) ) NEW_LINE