Count Occurrences in Sorted Array

Given a sorted array of integers and a target number x, your task is to count how many times the number x appears in the array.

• If the number is not found in the array, return 0.
• All elements in the array are sorted in non-decreasing order.
• You must use an efficient approach using binary search to find the count.

Understanding the Problem

We are given a sorted array and a number x. Our task is to count how many times x appears in that array.

Since the array is already sorted, we can make use of binary search to efficiently find the count, instead of scanning the entire array.

How We'll Solve It

We will solve this in three main steps:

1. Use binary search to find the first occurrence of x.
2. Use binary search again to find the last occurrence of x.
3. If x is found, compute the count as lastIndex - firstIndex + 1. Otherwise, return 0.

Example: Let's Understand with an Example

Consider the array [2, 4, 4, 4, 6, 8] and x = 4.

• First occurrence of 4 is at index 1.
• Last occurrence of 4 is at index 3.
• So the count is 3 - 1 + 1 = 3.

What About Edge Cases?

• Element appears only once:
  Array = [1, 2, 3, 4, 5], x = 3. First and last occurrence both at index 2 → count = 1.
• Element doesn't exist:
  Array = [1, 2, 4, 5], x = 3. Binary search returns -1 → count = 0.
• Element at the beginning:
  Array = [2, 2, 3, 4], x = 2. First at 0, last at 1 → count = 2.
• Element at the end:
  Array = [1, 2, 3, 4, 4], x = 4. First at 3, last at 4 → count = 2.
• Empty array:
  Array = [], any value of x → count = 0.

Why Use Binary Search?

Because the array is sorted, binary search lets us locate the first and last occurrences in O(log n) time.

If we used a regular linear scan, it would take O(n) time, which is much slower for large arrays.

Finally

This solution is efficient and elegant. By simply applying binary search twice, we can handle all normal and edge cases with minimal extra code.

It’s especially beginner-friendly because the logic is easy to break down: find first, find last, subtract the indices — and you’re done!

1. Use binary search to find the first occurrence of the key.
2. Use binary search again to find the last occurrence of the key.
3. If key is not found, return 0.
4. Otherwise, return lastIndex - firstIndex + 1.

#include <stdio.h>

int findFirst(int arr[], int n, int key) {
    int start = 0, end = n - 1, res = -1;
    while (start <= end) {
        int mid = start + (end - start) / 2;
        if (arr[mid] == key) {
            res = mid;
            end = mid - 1;
        } else if (arr[mid] < key) {
            start = mid + 1;
        } else {
            end = mid - 1;
        }
    }
    return res;
}

int findLast(int arr[], int n, int key) {
    int start = 0, end = n - 1, res = -1;
    while (start <= end) {
        int mid = start + (end - start) / 2;
        if (arr[mid] == key) {
            res = mid;
            start = mid + 1;
        } else if (arr[mid] < key) {
            start = mid + 1;
        } else {
            end = mid - 1;
        }
    }
    return res;
}

int countOccurrences(int arr[], int n, int key) {
    int first = findFirst(arr, n, key);
    int last = findLast(arr, n, key);
    if (first == -1) return 0;
    return last - first + 1;
}

int main() {
    int arr[] = {1, 2, 2, 2, 3, 4};
    int n = sizeof(arr)/sizeof(arr[0]);
    int key = 2;
    printf("Count of %d: %d\n", key, countOccurrences(arr, n, key));
    return 0;
}

#include <iostream>
using namespace std;

int findFirst(int arr[], int n, int key) {
    int start = 0, end = n - 1, res = -1;
    while (start <= end) {
        int mid = start + (end - start) / 2;
        if (arr[mid] == key) {
            res = mid;
            end = mid - 1;
        } else if (arr[mid] < key) {
            start = mid + 1;
        } else {
            end = mid - 1;
        }
    }
    return res;
}

int findLast(int arr[], int n, int key) {
    int start = 0, end = n - 1, res = -1;
    while (start <= end) {
        int mid = start + (end - start) / 2;
        if (arr[mid] == key) {
            res = mid;
            start = mid + 1;
        } else if (arr[mid] < key) {
            start = mid + 1;
        } else {
            end = mid - 1;
        }
    }
    return res;
}

int countOccurrences(int arr[], int n, int key) {
    int first = findFirst(arr, n, key);
    int last = findLast(arr, n, key);
    if (first == -1) return 0;
    return last - first + 1;
}

int main() {
    int arr[] = {1, 2, 2, 2, 3, 4};
    int n = sizeof(arr)/sizeof(arr[0]);
    int key = 2;
    cout << "Count of " << key << ": " << countOccurrences(arr, n, key) << endl;
    return 0;
}

def count_occurrences(arr, key):
    def find_first():
        start, end = 0, len(arr) - 1
        res = -1
        while start <= end:
            mid = (start + end) // 2
            if arr[mid] == key:
                res = mid
                end = mid - 1
            elif arr[mid] < key:
                start = mid + 1
            else:
                end = mid - 1
        return res

    def find_last():
        start, end = 0, len(arr) - 1
        res = -1
        while start <= end:
            mid = (start + end) // 2
            if arr[mid] == key:
                res = mid
                start = mid + 1
            elif arr[mid] < key:
                start = mid + 1
            else:
                end = mid - 1
        return res

    first = find_first()
    last = find_last()
    return last - first + 1 if first != -1 else 0

arr = [1, 2, 2, 2, 3, 4]
key = 2
print("Count of", key, ":", count_occurrences(arr, key))

public class CountOccurrences {

  public static int countOccurrences(int[] arr, int key) {
    int first = findFirst(arr, key);
    int last = findLast(arr, key);
    if (first == -1 || last == -1) return 0;
    return last - first + 1;
  }

  private static int findFirst(int[] arr, int key) {
    int start = 0, end = arr.length - 1, res = -1;
    while (start <= end) {
      int mid = start + (end - start) / 2;
      if (arr[mid] == key) {
        res = mid;
        end = mid - 1;
      } else if (arr[mid] < key) {
        start = mid + 1;
      } else {
        end = mid - 1;
      }
    }
    return res;
  }

  private static int findLast(int[] arr, int key) {
    int start = 0, end = arr.length - 1, res = -1;
    while (start <= end) {
      int mid = start + (end - start) / 2;
      if (arr[mid] == key) {
        res = mid;
        start = mid + 1;
      } else if (arr[mid] < key) {
        start = mid + 1;
      } else {
        end = mid - 1;
      }
    }
    return res;
  }

  public static void main(String[] args) {
    int[] arr = {1, 2, 2, 2, 3, 4};
    int key = 2;
    System.out.println("Count of " + key + ": " + countOccurrences(arr, key));
  }
}

function countOccurrences(arr, key) {
  function findFirst() {
    let start = 0, end = arr.length - 1, res = -1;
    while (start <= end) {
      const mid = Math.floor((start + end) / 2);
      if (arr[mid] === key) {
        res = mid;
        end = mid - 1;
      } else if (arr[mid] < key) {
        start = mid + 1;
      } else {
        end = mid - 1;
      }
    }
    return res;
  }

  function findLast() {
    let start = 0, end = arr.length - 1, res = -1;
    while (start <= end) {
      const mid = Math.floor((start + end) / 2);
      if (arr[mid] === key) {
        res = mid;
        start = mid + 1;
      } else if (arr[mid] < key) {
        start = mid + 1;
      } else {
        end = mid - 1;
      }
    }
    return res;
  }

  const first = findFirst();
  const last = findLast();
  return first === -1 ? 0 : last - first + 1;
}

const arr = [1, 2, 2, 2, 3, 4];
const key = 2;
console.log("Count of", key, ":", countOccurrences(arr, key));

package main

import (
  "fmt"
)

func findFirst(arr []int, key int) int {
  start, end, res := 0, len(arr)-1, -1
  for start <= end {
    mid := (start + end) / 2
    if arr[mid] == key {
      res = mid
      end = mid - 1
    } else if arr[mid] < key {
      start = mid + 1
    } else {
      end = mid - 1
    }
  }
  return res
}

func findLast(arr []int, key int) int {
  start, end, res := 0, len(arr)-1, -1
  for start <= end {
    mid := (start + end) / 2
    if arr[mid] == key {
      res = mid
      start = mid + 1
    } else if arr[mid] < key {
      start = mid + 1
    } else {
      end = mid - 1
    }
  }
  return res
}

func countOccurrences(arr []int, key int) int {
  first := findFirst(arr, key)
  last := findLast(arr, key)
  if first == -1 {
    return 0
  }
  return last - first + 1
}

func main() {
  arr := []int{1, 2, 2, 2, 3, 4}
  key := 2
  fmt.Printf("Count of %d: %d\n", key, countOccurrences(arr, key))
}

fn find_first(arr: &Vec<i32>, key: i32) -> i32 {
    let (mut start, mut end) = (0, arr.len() - 1);
    let mut res = -1;
    while start <= end {
        let mid = (start + end) / 2;
        if arr[mid] == key {
            res = mid as i32;
            if mid == 0 { break; }
            end = mid - 1;
        } else if arr[mid] < key {
            start = mid + 1;
        } else {
            if mid == 0 { break; }
            end = mid - 1;
        }
    }
    res
}

fn find_last(arr: &Vec<i32>, key: i32) -> i32 {
    let (mut start, mut end) = (0, arr.len() - 1);
    let mut res = -1;
    while start <= end {
        let mid = (start + end) / 2;
        if arr[mid] == key {
            res = mid as i32;
            start = mid + 1;
        } else if arr[mid] < key {
            start = mid + 1;
        } else {
            if mid == 0 { break; }
            end = mid - 1;
        }
    }
    res
}

fn count_occurrences(arr: Vec<i32>, key: i32) -> i32 {
    let first = find_first(&arr, key);
    let last = find_last(&arr, key);
    if first == -1 { 0 } else { last - first + 1 }
}

fn main() {
    let arr = vec![1, 2, 2, 2, 3, 4];
    let key = 2;
    println!("Count of {}: {}", key, count_occurrences(arr, key));
}

fun countOccurrences(arr: IntArray, key: Int): Int {
    fun findFirst(): Int {
        var start = 0
        var end = arr.size - 1
        var res = -1
        while (start <= end) {
            val mid = (start + end) / 2
            if (arr[mid] == key) {
                res = mid
                end = mid - 1
            } else if (arr[mid] < key) {
                start = mid + 1
            } else {
                end = mid - 1
            }
        }
        return res
    }

    fun findLast(): Int {
        var start = 0
        var end = arr.size - 1
        var res = -1
        while (start <= end) {
            val mid = (start + end) / 2
            if (arr[mid] == key) {
                res = mid
                start = mid + 1
            } else if (arr[mid] < key) {
                start = mid + 1
            } else {
                end = mid - 1
            }
        }
        return res
    }

    val first = findFirst()
    val last = findLast()
    return if (first == -1) 0 else last - first + 1
}

fun main() {
    val arr = intArrayOf(1, 2, 2, 2, 3, 4)
    val key = 2
    println("Count of $key: ${countOccurrences(arr, key)}")
}

func countOccurrences(_ arr: [Int], _ key: Int) -> Int {
    func findFirst() -> Int {
        var start = 0, end = arr.count - 1, res = -1
        while start <= end {
            let mid = (start + end) / 2
            if arr[mid] == key {
                res = mid
                end = mid - 1
            } else if arr[mid] < key {
                start = mid + 1
            } else {
                end = mid - 1
            }
        }
        return res
    }

    func findLast() -> Int {
        var start = 0, end = arr.count - 1, res = -1
        while start <= end {
            let mid = (start + end) / 2
            if arr[mid] == key {
                res = mid
                start = mid + 1
            } else if arr[mid] < key {
                start = mid + 1
            } else {
                end = mid - 1
            }
        }
        return res
    }

    let first = findFirst()
    let last = findLast()
    return first == -1 ? 0 : last - first + 1
}

let arr = [1, 2, 2, 2, 3, 4]
let key = 2
print("Count of \(key): \(countOccurrences(arr, key))")

function countOccurrences(arr: number[], key: number): number {
  function findFirst(): number {
    let start = 0, end = arr.length - 1, res = -1;
    while (start <= end) {
      const mid = Math.floor((start + end) / 2);
      if (arr[mid] === key) {
        res = mid;
        end = mid - 1;
      } else if (arr[mid] < key) {
        start = mid + 1;
      } else {
        end = mid - 1;
      }
    }
    return res;
  }

  function findLast(): number {
    let start = 0, end = arr.length - 1, res = -1;
    while (start <= end) {
      const mid = Math.floor((start + end) / 2);
      if (arr[mid] === key) {
        res = mid;
        start = mid + 1;
      } else if (arr[mid] < key) {
        start = mid + 1;
      } else {
        end = mid - 1;
      }
    }
    return res;
  }

  const first = findFirst();
  const last = findLast();
  return first === -1 ? 0 : last - first + 1;
}

const arr: number[] = [1, 2, 2, 2, 3, 4];
const key: number = 2;
console.log(`Count of ${key}: ${countOccurrences(arr, key)}`);

Time complexity

Space complexity

O(1)

Only a few variables are used; no extra space is needed.