void bubbleSortOptimized(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        bool swapped = false;
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]);
                swapped = true;
            }
        }
        if (!swapped) break;
    }
}

“A year from now you may wish you had
started today”

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        def first():
            l, r = 0, len(nums)-1
            first = -1 
            while l <= r:
                mid = (l+r)//2
                if nums[mid] == target:
                    first = mid
                    r = mid - 1
                elif nums[mid] < target:
                    l = mid + 1
                else:
                    r = mid - 1
            return first
        def last():
            l, r = 0, len(nums)-1
            last = -1 
            while l <= r:
                mid = (l+r)//2
                if nums[mid] == target:
                    last = mid
                    l = mid + 1
                elif nums[mid] < target:
                    l = mid + 1
                else:
                    r = mid - 1
            return last

        f = first()
        if f == - 1: return [-1, -1]
        la = last()
        return [f, la]

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        def lower_bound():
            l, r = 0, len(nums)-1
            ans = len(nums)
            while l <= r:
                mid = (l+r)//2
                if nums[mid] >= target:
                    ans = mid
                    r = mid - 1
                else:
                    l = mid + 1
            return ans
        def upper_bound():
            l, r = 0, len(nums)-1
            ans = len(nums)
            while l <= r:
                mid = (l+r)//2
                if nums[mid] > target:
                    ans = mid
                    r = mid - 1
                else:
                    l = mid + 1
            return ans
        
        lb = lower_bound()
        up = upper_bound() - 1
        if lb <= up:
            return [lb, up]
        return [-1, -1]

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        lb = bisect.bisect_left(nums, target)
        if lb >= len(nums) or nums[lb] != target:
            return [-1, -1]
        ub = bisect.bisect_right(nums, target)
        return [lb, ub-1]
    

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        auto lb = lower_bound(nums.begin(), nums.end(), target) - nums.begin();
        if (lb >= nums.size() || nums[lb] != target)
            return {-1, -1};
        auto ub = upper_bound(nums.begin(), nums.end(), target) - nums.begin();
        return {(int)lb, (int)ub-1};
    }
};

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        row = len(matrix)
        col = len(matrix[0])
        l, r = 0, (row * col) - 1
        while l <= r:
            mid = (l+r)//2
            # i = mid // col
            # j = mid % col
            i, j = divmod(mid, col) # one liner for the above
            if matrix[i][j] == target:
                return True
            elif target >= matrix[i][j]:
                l = mid + 1
            else:
                r = mid - 1
        return False

Time complexity = O(n×log(maxDays)) ; Space complexity = O(1)

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        max_days = max(bloomDay)
        min_days = -1
        L, R = 0, max_days
        while L <= R:
            mid = (L+R)//2
            count = 0
            m_count = 0
            for bloom in bloomDay:
                if mid >= bloom:
                    count += 1
                    if count >= k:
                        m_count += 1
                        count = 0
                else:
                    count = 0
            if m_count >= m:
                min_days = mid
                R = mid - 1  
            else:
                L = mid + 1
            
        return min_days

class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        max_num = max(nums)
        divisor = max_num
        L, R = 1, max_num # make sure to start from 1, if L = 0 we might encounter a runtime error, division by zero
        while L <= R:
            mid = (L+R)//2

            total_sum = sum((num + mid - 1)//mid for num in nums)
           # math.ceil(num / mid) is the same as (num+mid-1)//mid, the second on is more facter on CPU.
            if total_sum <= threshold:
                divisor = mid
                R = mid - 1
            else:
                L = mid + 1
        return divisor