Total Occurrences of k in a sorted array

first: liner scan, time O(n) space O(1)

two : binary search & liner scan. Time: O(logn)+O(n) = O(n) , sapce O(1)

thre binary search . O(logn)

binary search: mid = left+(right-left) / 2, don’t using (left+right) /2 it will overflow