Given a sorted bit array (values of either 0 or 1), determine the number of 1’s in the array.

sorted_bit_array_num_ones.swift

//Given a sorted bit array (values of either 0 or 1), determine the number of 1’s in the array.
//
//Perform this in O(log(N)) time complexity.
//
//Input: [0,0,0,1,1,1,1,1,1,1,1]
//
//Output: 8

func numOnes(_ arr: [Int]) -> Int {

    func binSearch(left: Int, right: Int) -> Int {
        var left = left, right = right
        while (left + 1 < right) {
            let middle = (left + right) / 2
            if arr[middle] == arr[right] {
                right = middle
            } else {
                left = middle
            }
        }

        return right
    }

    let firstOneIdx = binSearch(left: 0, right: arr.count - 1)

    return arr.count - firstOneIdx
}