How I intuitively prove the time complexity of this piece of code

Question

I have fragment code as follows:

int searchNumOccurrence(vector<int> &V, int k, int start, int end) {
    if (start > end) return 0;
    int mid = (start + end) / 2;
    if (V[mid] < k) return searchNumOccurrence(V, k, mid + 1, end);
    if (V[mid] > k) return searchNumOccurrence(V, k, start, mid - 1);
    return searchNumOccurrence(V, k, start, mid - 1) + 1 +       searchNumOccurrence(V, k, mid + 1, end);
}

By analyzing intuitively, suppose that all numbers in the array are equal = k. This would mean that we could again and again go back to recursion in return searchNumOccurrence(V, k, start, mid - 1). Assuming my start was 0 and end was N, this will execute Log (N) times. The same for the left side and the answer will be * (2 * Log (n))) = Log (n).

However, the answer to this question is O (N). Although a theoretical proof would be fine, I really want to understand how this happens in O (N) intuitively.

thank

Answer 1

: : , , . O (1), n O (n).

: . ( , "" ). O(log n), - O(2^i), i - . , O(2^log(n)) O(n).

Answer 2

, A 42, 1000 . searchNumOccurrence(A, 42, 0, 999) 1000. , 1000, "+ 1" . , 1000 = N .

, O (log N).