Binary Search in a Sorted Array

int binarySearch(vector& arr, int target) {
    int left = 0, right = arr.size() - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}
            

Find First and Last Position of an Element in a Sorted Array

vector searchRange(vector& nums, int target) {
    vector result = {-1, -1};
    int left = 0, right = nums.size() - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            result[0] = mid;
            result[1] = mid;
            while (result[0] > 0 && nums[result[0] - 1] == target) result[0]--;
            while (result[1] < nums.size() - 1 && nums[result[1] + 1] == target) result[1]++;
            break;
        } else if (nums[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return result;
}
            

Search a 2D Matrix

bool searchMatrix(vector>& matrix, int target) {
    int rows = matrix.size();
    int cols = matrix[0].size();
    int left = 0, right = rows * cols - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        int midVal = matrix[mid / cols][mid % cols];
        if (midVal == target) return true;
        else if (midVal < target) left = mid + 1;
        else right = mid - 1;
    }
    return false;
}
            

Find the Square Root of a Number

int mySqrt(int x) {
    long left = 0, right = x;
    while (left <= right) {
        long mid = left + (right - left) / 2;
        if (mid * mid == x) return mid;
        else if (mid * mid < x) left = mid + 1;
        else right = mid - 1;
    }
    return right;
}
            

Find the Peak Element in an Array

int findPeakElement(vector& nums) {
    int left = 0, right = nums.size() - 1;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] > nums[mid + 1]) right = mid;
        else left = mid + 1;
    }
    return left;
}
            

Find the Minimum Element in a Rotated Sorted Array

int findMin(vector& nums) {
    int left = 0, right = nums.size() - 1;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] > nums[right]) left = mid + 1;
        else right = mid;
    }
    return nums[left];
}
            

Find the Element in a Rotated Sorted Array

int search(vector& nums, int target) {
    int left = 0, right = nums.size() - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) return mid;
        if (nums[left] <= nums[mid]) {
            if (nums[left] <= target && target < nums[mid]) right = mid - 1;
            else left = mid + 1;
        } else {
            if (nums[mid] < target && target <= nums[right]) left = mid + 1;
            else right = mid - 1;
        }
    }
    return -1;
}
            

Find the Number of Occurrences of an Element in a Sorted Array

int countOccurrences(vector& nums, int target) {
    int first = binarySearch(nums, target);
    if (first == -1) return 0;
    int last = binarySearch(nums, target);
    return last - first + 1;
}

int binarySearch(vector& nums, int target) {
    int left = 0, right = nums.size() - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) return mid;
        else if (nums[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}
            

Find the Kth Smallest Element in a Sorted Matrix

int kthSmallest(vector>& matrix, int k) {
    int n = matrix.size(), m = matrix[0].size();
    int left = matrix[0][0], right = matrix[n-1][m-1];
    while (left < right) {
        int mid = left + (right - left) / 2;
        int count = 0;
        for (int i = 0; i < n; i++) {
            count += upper_bound(matrix[i].begin(), matrix[i].end(), mid) - matrix[i].begin();
        }
        if (count < k) left = mid + 1;
        else right = mid;
    }
    return left;
}