Count of Element in Sorted Array 🎯

Welcome back to CodeYourCraft! Today, we're going to learn about finding the count of an element in a sorted array. This is a fundamental concept in computer science that you'll find useful in many real-world projects. Let's get started!

Understanding the Problem 📝

Given a sorted array, the task is to find the frequency or count of an element.

Breaking it Down 💡

To solve this problem, we'll use the concept of binary search. Binary search is an efficient search algorithm that works on sorted arrays. It divides the array into two halves repeatedly, and each time, it discards the half that cannot contain the target element.

Pseudo-code 💡

Here's the high-level approach to solve the problem:

Initialize two pointers, low and high, to the first and last index of the array, respectively.
Calculate the middle index, mid, using the formula: mid = (low + high) / 2.
Compare the middle element with the target element.
If the middle element is equal to the target, return its count.
If the target is greater than the middle element, update low to mid + 1.
If the target is less than the middle element, update high to mid - 1.
Repeat steps 2-6 until low <= high.

Code Examples ✅

Python

python

def count_element(arr, target):
    count = 0
    low, high = 0, len(arr) - 1

    while low <= high:
        mid = (low + high) // 2

        if arr[mid] == target:
            count += 1
            low = mid + 1
        elif arr[mid] > target:
            high = mid - 1
        else:
            low = mid + 1

    return count

JavaScript

javascript

function countElement(arr, target) {
    let count = 0;
    let low = 0, high = arr.length - 1;

    while (low <= high) {
        const mid = Math.floor((low + high) / 2);

        if (arr[mid] === target) {
            count++;
            low = mid + 1;
        } else if (arr[mid] > target) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }

    return count;
}

Quiz Time 💡

That's it for today's lesson on finding the count of an element in a sorted array. Practice these code examples, and you'll be able to solve this problem in various programming languages.

See you in the next lesson! 🚀