// TypeScript - Bubble Sort
function bubbleSort(arr: number[]): number[] {
  const n = arr.length;
  for (let i = 0; i < n - 1; i++) {
    let swapped = false;
    for (let j = 0; j < n - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
        swapped = true;
      }
    }
    // Tối ưu: nếu không swap, array đã sorted
    if (!swapped) break;
  }
  return arr;
}
 
console.log(bubbleSort([5, 3, 8, 1, 2])); // [1, 2, 3, 5, 8]

# Python - Bubble Sort
def bubble_sort(arr: list[int]) -> list[int]:
    n = len(arr)
    for i in range(n - 1):
        swapped = False
        for j in range(n - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        # Tối ưu: nếu không swap, array đã sorted
        if not swapped:
            break
    return arr
 
print(bubble_sort([5, 3, 8, 1, 2]))  # [1, 2, 3, 5, 8]

// TypeScript - Selection Sort
function selectionSort(arr: number[]): number[] {
  const n = arr.length;
  for (let i = 0; i < n - 1; i++) {
    let minIdx = i;
    for (let j = i + 1; j < n; j++) {
      if (arr[j] < arr[minIdx]) {
        minIdx = j;
      }
    }
    if (minIdx !== i) {
      [arr[i], arr[minIdx]] = [arr[minIdx], arr[i]];
    }
  }
  return arr;
}

# Python - Selection Sort
def selection_sort(arr: list[int]) -> list[int]:
    n = len(arr)
    for i in range(n - 1):
        min_idx = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        if min_idx != i:
            arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

// TypeScript - Insertion Sort
function insertionSort(arr: number[]): number[] {
  const n = arr.length;
  for (let i = 1; i < n; i++) {
    const key = arr[i];
    let j = i - 1;
    // Dịch các phần tử lớn hơn key sang phải
    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = key;
  }
  return arr;
}

# Python - Insertion Sort
def insertion_sort(arr: list[int]) -> list[int]:
    n = len(arr)
    for i in range(1, n):
        key = arr[i]
        j = i - 1
        # Dịch các phần tử lớn hơn key sang phải
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

// TypeScript - Merge Sort
function mergeSort(arr: number[]): number[] {
  if (arr.length <= 1) return arr;
 
  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));
 
  return merge(left, right);
}
 
function merge(left: number[], right: number[]): number[] {
  const result: number[] = [];
  let i = 0, j = 0;
 
  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) {
      result.push(left[i]);
      i++;
    } else {
      result.push(right[j]);
      j++;
    }
  }
 
  // Thêm các phần tử còn lại
  while (i < left.length) result.push(left[i++]);
  while (j < right.length) result.push(right[j++]);
 
  return result;
}
 
console.log(mergeSort([38, 27, 43, 3, 9, 82, 10]));
// [3, 9, 10, 27, 38, 43, 82]

# Python - Merge Sort
def merge_sort(arr: list[int]) -> list[int]:
    if len(arr) <= 1:
        return arr
 
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
 
    return merge(left, right)
 
def merge(left: list[int], right: list[int]) -> list[int]:
    result = []
    i = j = 0
 
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
 
    # Thêm các phần tử còn lại
    result.extend(left[i:])
    result.extend(right[j:])
    return result
 
print(merge_sort([38, 27, 43, 3, 9, 82, 10]))
# [3, 9, 10, 27, 38, 43, 82]

Left:  [3, 27, 38, 43]    Right: [9, 10, 82]
        ↑ i=0                      ↑ j=0
 
Step 1: 3 < 9   → lấy 3    Result: [3]
Step 2: 27 > 9  → lấy 9    Result: [3, 9]
Step 3: 27 > 10 → lấy 10   Result: [3, 9, 10]
Step 4: 27 < 82 → lấy 27   Result: [3, 9, 10, 27]
Step 5: 38 < 82 → lấy 38   Result: [3, 9, 10, 27, 38]
Step 6: 43 < 82 → lấy 43   Result: [3, 9, 10, 27, 38, 43]
Step 7: thêm 82             Result: [3, 9, 10, 27, 38, 43, 82]

// TypeScript - Quick Sort (Lomuto partition)
function quickSort(arr: number[], low: number = 0, high: number = arr.length - 1): number[] {
  if (low < high) {
    const pivotIdx = partition(arr, low, high);
    quickSort(arr, low, pivotIdx - 1);
    quickSort(arr, pivotIdx + 1, high);
  }
  return arr;
}
 
function partition(arr: number[], low: number, high: number): number {
  const pivot = arr[high]; // Chọn phần tử cuối làm pivot
  let i = low - 1;        // Ranh giới phần tử nhỏ hơn
 
  for (let j = low; j < high; j++) {
    if (arr[j] <= pivot) {
      i++;
      [arr[i], arr[j]] = [arr[j], arr[i]];
    }
  }
 
  // Đặt pivot vào đúng vị trí
  [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
  return i + 1;
}
 
console.log(quickSort([8, 3, 1, 7, 0, 10, 2]));
// [0, 1, 2, 3, 7, 8, 10]

# Python - Quick Sort (Lomuto partition)
def quick_sort(arr: list[int], low: int = 0, high: int = None) -> list[int]:
    if high is None:
        high = len(arr) - 1
 
    if low < high:
        pivot_idx = partition(arr, low, high)
        quick_sort(arr, low, pivot_idx - 1)
        quick_sort(arr, pivot_idx + 1, high)
 
    return arr
 
def partition(arr: list[int], low: int, high: int) -> int:
    pivot = arr[high]  # Chọn phần tử cuối làm pivot
    i = low - 1        # Ranh giới phần tử nhỏ hơn
 
    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
 
    # Đặt pivot vào đúng vị trí
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1
 
print(quick_sort([8, 3, 1, 7, 0, 10, 2]))
# [0, 1, 2, 3, 7, 8, 10]

Ban đầu: [8, 3, 1, 7, 0, 10, 2]  pivot=2, i=-1
 
j=0: 8 > 2  → bỏ qua
j=1: 3 > 2  → bỏ qua
j=2: 1 ≤ 2  → i=0, swap(0,2) → [1, 3, 8, 7, 0, 10, 2]
j=3: 7 > 2  → bỏ qua
j=4: 0 ≤ 2  → i=1, swap(1,4) → [1, 0, 8, 7, 3, 10, 2]
j=5: 10 > 2 → bỏ qua
 
Đặt pivot: swap(i+1=2, high=6) → [1, 0, 2, 7, 3, 10, 8]
                                          ↑ pivot tại index 2

// TypeScript/JavaScript - TimSort (stable, O(n log n))
const arr = [3, 1, 4, 1, 5, 9];
arr.sort((a, b) => a - b);  // Luôn cung cấp comparator cho số!
// Không có comparator, JS sort theo string: [1, 1, 3, 4, 5, 9]

# Python - TimSort (stable, O(n log n))
arr = [3, 1, 4, 1, 5, 9]
arr.sort()              # Sort in-place
sorted_arr = sorted(arr)  # Trả về list mới đã sorted
 
# Custom sort
intervals = [(2, 3), (1, 5), (1, 2)]
intervals.sort(key=lambda x: (x[0], x[1]))
# [(1, 2), (1, 5), (2, 3)]

Linear Search:  [1, 3, 5, 7, 9, 11, 13, 15]  → Kiểm tra từng cái: O(n)
Binary Search:  [1, 3, 5, 7, 9, 11, 13, 15]  → Kiểm tra giữa, loại nửa: O(log n)

// TypeScript - Standard Binary Search
function binarySearch(arr: number[], target: number): number {
  let left = 0;
  let right = arr.length - 1;
 
  while (left <= right) {
    const mid = Math.floor(left + (right - left) / 2); // Tránh overflow
 
    if (arr[mid] === target) {
      return mid;      // Tìm thấy
    } else if (arr[mid] < target) {
      left = mid + 1;  // Target ở nửa phải
    } else {
      right = mid - 1; // Target ở nửa trái
    }
  }
 
  return -1; // Không tìm thấy
}
 
console.log(binarySearch([1, 3, 5, 7, 9, 11], 7));  // 3
console.log(binarySearch([1, 3, 5, 7, 9, 11], 6));  // -1

# Python - Standard Binary Search
def binary_search(arr: list[int], target: int) -> int:
    left, right = 0, len(arr) - 1
 
    while left <= right:
        mid = left + (right - left) // 2  # Tránh overflow
 
        if arr[mid] == target:
            return mid       # Tìm thấy
        elif arr[mid] < target:
            left = mid + 1   # Target ở nửa phải
        else:
            right = mid - 1  # Target ở nửa trái
 
    return -1  # Không tìm thấy
 
print(binary_search([1, 3, 5, 7, 9, 11], 7))   # 3
print(binary_search([1, 3, 5, 7, 9, 11], 6))   # -1

Step 1: left=0, right=5, mid=2 → arr[2]=5 < 7  → left=3
Step 2: left=3, right=5, mid=4 → arr[4]=9 > 7  → right=3
Step 3: left=3, right=3, mid=3 → arr[3]=7 = 7  → return 3 ✓

// TypeScript - Tìm vị trí đầu tiên arr[mid] >= target
function lowerBound(arr: number[], target: number): number {
  let left = 0;
  let right = arr.length; // Lưu ý: right = length (không phải length-1)
 
  while (left < right) {  // Lưu ý: < chặt (không phải <=)
    const mid = Math.floor(left + (right - left) / 2);
    if (arr[mid] < target) {
      left = mid + 1;
    } else {
      right = mid;  // Lưu ý: right = mid (không phải mid-1)
    }
  }
 
  return left; // Vị trí đầu tiên arr[left] >= target
}
 
// Ví dụ: [1, 3, 3, 5, 7]
// lowerBound(arr, 3) → 1 (index đầu tiên có giá trị >= 3)
// lowerBound(arr, 4) → 3 (index đầu tiên có giá trị >= 4, tức là 5)
// lowerBound(arr, 8) → 5 (vượt quá cuối, target > tất cả phần tử)

# Python - Tìm vị trí đầu tiên arr[mid] >= target
def lower_bound(arr: list[int], target: int) -> int:
    left, right = 0, len(arr)  # right = len(arr), không phải len(arr)-1
 
    while left < right:  # < chặt (không phải <=)
        mid = left + (right - left) // 2
        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid  # right = mid (không phải mid-1)
 
    return left  # Vị trí đầu tiên arr[left] >= target
 
# Python cũng có built-in:
import bisect
bisect.bisect_left([1, 3, 3, 5, 7], 3)   # 1
bisect.bisect_right([1, 3, 3, 5, 7], 3)  # 3

// TypeScript - Tìm vị trí cuối cùng arr[mid] <= target
function upperBound(arr: number[], target: number): number {
  let left = 0;
  let right = arr.length;
 
  while (left < right) {
    const mid = Math.floor(left + (right - left) / 2);
    if (arr[mid] <= target) {
      left = mid + 1;
    } else {
      right = mid;
    }
  }
 
  return left - 1; // Vị trí cuối cùng arr[left-1] <= target
}
 
// Ví dụ: [1, 3, 3, 5, 7]
// upperBound(arr, 3) → 2 (index cuối có giá trị <= 3)
// upperBound(arr, 4) → 2 (index cuối có giá trị <= 4, tức là 3)

Answer space:  [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
canAchieve:    [F, F, F, F, T, T, T, T, T, T]
                              ↑ Tìm boundary này

// TypeScript - Binary Search on Answer template
function binarySearchOnAnswer(low: number, high: number): number {
  while (low < high) {
    const mid = Math.floor(low + (high - low) / 2);
    if (canAchieve(mid)) {
      high = mid;     // mid có thể là answer, search bên trái
    } else {
      low = mid + 1;  // mid quá nhỏ, search bên phải
    }
  }
  return low;
}

# Python - Binary Search on Answer template
def binary_search_on_answer(low: int, high: int) -> int:
    while low < high:
        mid = low + (high - low) // 2
        if can_achieve(mid):
            high = mid      # mid có thể là answer, search bên trái
        else:
            low = mid + 1   # mid quá nhỏ, search bên phải
    return low

// TypeScript - Sort Colors (One-pass, O(n) time, O(1) space)
function sortColors(nums: number[]): void {
  let low = 0;      // Ranh giới: mọi thứ trước low là 0
  let mid = 0;      // Phần tử hiện tại
  let high = nums.length - 1; // Ranh giới: mọi thứ sau high là 2
 
  while (mid <= high) {
    if (nums[mid] === 0) {
      [nums[low], nums[mid]] = [nums[mid], nums[low]];
      low++;
      mid++;
    } else if (nums[mid] === 1) {
      mid++;
    } else {
      // nums[mid] === 2
      [nums[mid], nums[high]] = [nums[high], nums[mid]];
      high--;
      // Không tăng mid — phần tử swap cần kiểm tra lại
    }
  }
}
 
const colors = [2, 0, 2, 1, 1, 0];
sortColors(colors);
console.log(colors); // [0, 0, 1, 1, 2, 2]

# Python - Sort Colors (One-pass, O(n) time, O(1) space)
def sort_colors(nums: list[int]) -> None:
    low, mid, high = 0, 0, len(nums) - 1
 
    while mid <= high:
        if nums[mid] == 0:
            nums[low], nums[mid] = nums[mid], nums[low]
            low += 1
            mid += 1
        elif nums[mid] == 1:
            mid += 1
        else:
            nums[mid], nums[high] = nums[high], nums[mid]
            high -= 1
            # Không tăng mid — phần tử swap cần kiểm tra lại
 
colors = [2, 0, 2, 1, 1, 0]
sort_colors(colors)
print(colors)  # [0, 0, 1, 1, 2, 2]

[2, 0, 2, 1, 1, 0]  low=0, mid=0, high=5
 ↑mid         ↑high
nums[0]=2 → swap(0,5) → [0, 0, 2, 1, 1, 2]  high=4
 
[0, 0, 2, 1, 1, 2]  low=0, mid=0, high=4
 ↑mid      ↑high
nums[0]=0 → swap(0,0) → [0, 0, 2, 1, 1, 2]  low=1, mid=1
 
nums[1]=0 → swap(1,1) → [0, 0, 2, 1, 1, 2]  low=2, mid=2
 
nums[2]=2 → swap(2,4) → [0, 0, 1, 1, 2, 2]  high=3
 
nums[2]=1 → mid=3
 
nums[3]=1 → mid=4  → mid > high → XONG ✓
Kết quả: [0, 0, 1, 1, 2, 2]

// TypeScript - Merge Intervals
function mergeIntervals(intervals: number[][]): number[][] {
  if (intervals.length <= 1) return intervals;
 
  // Sort theo start time
  intervals.sort((a, b) => a[0] - b[0]);
 
  const merged: number[][] = [intervals[0]];
 
  for (let i = 1; i < intervals.length; i++) {
    const current = intervals[i];
    const last = merged[merged.length - 1];
 
    if (current[0] <= last[1]) {
      // Chồng nhau — mở rộng điểm cuối
      last[1] = Math.max(last[1], current[1]);
    } else {
      // Không chồng — thêm interval mới
      merged.push(current);
    }
  }
 
  return merged;
}
 
console.log(mergeIntervals([[1,3],[2,6],[8,10],[15,18]]));
// [[1,6],[8,10],[15,18]]

# Python - Merge Intervals
def merge_intervals(intervals: list[list[int]]) -> list[list[int]]:
    if len(intervals) <= 1:
        return intervals
 
    # Sort theo start time
    intervals.sort(key=lambda x: x[0])
 
    merged = [intervals[0]]
 
    for current in intervals[1:]:
        last = merged[-1]
 
        if current[0] <= last[1]:
            # Chồng nhau — mở rộng điểm cuối
            last[1] = max(last[1], current[1])
        else:
            # Không chồng — thêm interval mới
            merged.append(current)
 
    return merged
 
print(merge_intervals([[1,3],[2,6],[8,10],[15,18]]))
# [[1,6],[8,10],[15,18]]

// TypeScript - Kth Largest Element (Quick Select)
function findKthLargest(nums: number[], k: number): number {
  // Lớn thứ k = nhỏ thứ (n - k) (0-indexed)
  const targetIdx = nums.length - k;
  return quickSelect(nums, 0, nums.length - 1, targetIdx);
}
 
function quickSelect(arr: number[], low: number, high: number, target: number): number {
  if (low === high) return arr[low];
 
  // Random pivot để tránh worst case
  const randomIdx = low + Math.floor(Math.random() * (high - low + 1));
  [arr[randomIdx], arr[high]] = [arr[high], arr[randomIdx]];
 
  const pivotIdx = partition(arr, low, high);
 
  if (pivotIdx === target) {
    return arr[pivotIdx];
  } else if (pivotIdx < target) {
    return quickSelect(arr, pivotIdx + 1, high, target);
  } else {
    return quickSelect(arr, low, pivotIdx - 1, target);
  }
}
 
// Tái sử dụng hàm partition từ Quick Sort (Mục 4.2)
 
console.log(findKthLargest([3, 2, 1, 5, 6, 4], 2)); // 5
console.log(findKthLargest([3, 2, 3, 1, 2, 4, 5, 5, 6], 4)); // 4

# Python - Kth Largest Element (Quick Select)
import random
 
def find_kth_largest(nums: list[int], k: int) -> int:
    target_idx = len(nums) - k  # Lớn thứ k = nhỏ thứ (n-k)
    return quick_select(nums, 0, len(nums) - 1, target_idx)
 
def quick_select(arr: list[int], low: int, high: int, target: int) -> int:
    if low == high:
        return arr[low]
 
    # Random pivot để tránh worst case
    random_idx = random.randint(low, high)
    arr[random_idx], arr[high] = arr[high], arr[random_idx]
 
    pivot_idx = qs_partition(arr, low, high)
 
    if pivot_idx == target:
        return arr[pivot_idx]
    elif pivot_idx < target:
        return quick_select(arr, pivot_idx + 1, high, target)
    else:
        return quick_select(arr, low, pivot_idx - 1, target)
 
def qs_partition(arr: list[int], low: int, high: int) -> int:
    pivot = arr[high]
    i = low - 1
    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1
 
print(find_kth_largest([3, 2, 1, 5, 6, 4], 2))  # 5

Sorted ban đầu: [0, 1, 2, 4, 5, 6, 7]
Rotated tại idx 4: [4, 5, 6, 7, 0, 1, 2]
                     ↑ sorted ↑  ↑ sorted ↑

// TypeScript - Search in Rotated Sorted Array
function searchRotated(nums: number[], target: number): number {
  let left = 0;
  let right = nums.length - 1;
 
  while (left <= right) {
    const mid = Math.floor(left + (right - left) / 2);
 
    if (nums[mid] === target) return mid;
 
    // Xác định nửa nào sorted
    if (nums[left] <= nums[mid]) {
      // Nửa trái sorted
      if (nums[left] <= target && target < nums[mid]) {
        right = mid - 1; // Target trong nửa trái sorted
      } else {
        left = mid + 1;  // Target trong nửa phải
      }
    } else {
      // Nửa phải sorted
      if (nums[mid] < target && target <= nums[right]) {
        left = mid + 1;  // Target trong nửa phải sorted
      } else {
        right = mid - 1; // Target trong nửa trái
      }
    }
  }
 
  return -1;
}
 
console.log(searchRotated([4, 5, 6, 7, 0, 1, 2], 0)); // 4
console.log(searchRotated([4, 5, 6, 7, 0, 1, 2], 3)); // -1

# Python - Search in Rotated Sorted Array
def search_rotated(nums: list[int], target: int) -> int:
    left, right = 0, len(nums) - 1
 
    while left <= right:
        mid = left + (right - left) // 2
 
        if nums[mid] == target:
            return mid
 
        # Xác định nửa nào sorted
        if nums[left] <= nums[mid]:
            # Nửa trái sorted
            if nums[left] <= target < nums[mid]:
                right = mid - 1  # Target trong nửa trái sorted
            else:
                left = mid + 1   # Target trong nửa phải
        else:
            # Nửa phải sorted
            if nums[mid] < target <= nums[right]:
                left = mid + 1   # Target trong nửa phải sorted
            else:
                right = mid - 1  # Target trong nửa trái
 
    return -1
 
print(search_rotated([4, 5, 6, 7, 0, 1, 2], 0))  # 4

Step 1: left=0, right=6, mid=3 → nums[3]=7 ≠ 0
        nums[0]=4 <= nums[3]=7 → nửa trái sorted [4,5,6,7]
        0 không trong [4, 7) → left = 4
 
Step 2: left=4, right=6, mid=5 → nums[5]=1 ≠ 0
        nums[4]=0 <= nums[5]=1 → nửa trái sorted [0,1]
        0 trong [0, 1) → right = 4
 
Step 3: left=4, right=4, mid=4 → nums[4]=0 = 0 → return 4 ✓

// TypeScript - Find First and Last Position
function searchRange(nums: number[], target: number): number[] {
  return [findFirst(nums, target), findLast(nums, target)];
}
 
function findFirst(nums: number[], target: number): number {
  let left = 0, right = nums.length - 1;
  let result = -1;
 
  while (left <= right) {
    const mid = Math.floor(left + (right - left) / 2);
    if (nums[mid] === target) {
      result = mid;
      right = mid - 1;  // Tiếp tục tìm bên trái cho occurrence sớm hơn
    } else if (nums[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
 
  return result;
}
 
function findLast(nums: number[], target: number): number {
  let left = 0, right = nums.length - 1;
  let result = -1;
 
  while (left <= right) {
    const mid = Math.floor(left + (right - left) / 2);
    if (nums[mid] === target) {
      result = mid;
      left = mid + 1;   // Tiếp tục tìm bên phải cho occurrence muộn hơn
    } else if (nums[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
 
  return result;
}
 
console.log(searchRange([5,7,7,8,8,10], 8)); // [3, 4]
console.log(searchRange([5,7,7,8,8,10], 6)); // [-1, -1]

# Python - Find First and Last Position
def search_range(nums: list[int], target: int) -> list[int]:
    return [find_first(nums, target), find_last(nums, target)]
 
def find_first(nums: list[int], target: int) -> int:
    left, right = 0, len(nums) - 1
    result = -1
 
    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] == target:
            result = mid
            right = mid - 1  # Tiếp tục tìm bên trái
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
 
    return result
 
def find_last(nums: list[int], target: int) -> int:
    left, right = 0, len(nums) - 1
    result = -1
 
    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] == target:
            result = mid
            left = mid + 1  # Tiếp tục tìm bên phải
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
 
    return result
 
print(search_range([5,7,7,8,8,10], 8))  # [3, 4]

// TypeScript - Find Peak Element
function findPeakElement(nums: number[]): number {
  let left = 0;
  let right = nums.length - 1;
 
  while (left < right) {
    const mid = Math.floor(left + (right - left) / 2);
 
    if (nums[mid] < nums[mid + 1]) {
      left = mid + 1;  // Peak ở bên phải
    } else {
      right = mid;     // Peak ở mid hoặc bên trái
    }
  }
 
  return left; // left === right, trỏ đến peak
}
 
console.log(findPeakElement([1, 2, 3, 1]));    // 2 (giá trị 3)
console.log(findPeakElement([1, 2, 1, 3, 5, 6, 4])); // 5 (giá trị 6)

# Python - Find Peak Element
def find_peak_element(nums: list[int]) -> int:
    left, right = 0, len(nums) - 1
 
    while left < right:
        mid = left + (right - left) // 2
 
        if nums[mid] < nums[mid + 1]:
            left = mid + 1   # Peak ở bên phải
        else:
            right = mid      # Peak ở mid hoặc bên trái
 
    return left  # left == right, trỏ đến peak
 
print(find_peak_element([1, 2, 3, 1]))    # 2
print(find_peak_element([1, 2, 1, 3, 5, 6, 4]))  # 5

// TypeScript - Find Minimum in Rotated Sorted Array
function findMin(nums: number[]): number {
  let left = 0;
  let right = nums.length - 1;
 
  while (left < right) {
    const mid = Math.floor(left + (right - left) / 2);
 
    if (nums[mid] > nums[right]) {
      left = mid + 1;  // Minimum ở nửa phải
    } else {
      right = mid;     // Minimum ở mid hoặc nửa trái
    }
  }
 
  return nums[left];
}
 
console.log(findMin([3, 4, 5, 1, 2]));    // 1
console.log(findMin([4, 5, 6, 7, 0, 1, 2])); // 0
console.log(findMin([11, 13, 15, 17]));    // 11 (không rotated)

# Python - Find Minimum in Rotated Sorted Array
def find_min(nums: list[int]) -> int:
    left, right = 0, len(nums) - 1
 
    while left < right:
        mid = left + (right - left) // 2
 
        if nums[mid] > nums[right]:
            left = mid + 1   # Minimum ở nửa phải
        else:
            right = mid      # Minimum ở mid hoặc nửa trái
 
    return nums[left]
 
print(find_min([3, 4, 5, 1, 2]))      # 1
print(find_min([4, 5, 6, 7, 0, 1, 2]))  # 0

// TypeScript - Koko Eating Bananas
function minEatingSpeed(piles: number[], h: number): number {
  let left = 1;
  let right = Math.max(...piles);
 
  while (left < right) {
    const mid = Math.floor(left + (right - left) / 2);
 
    if (canFinish(piles, mid, h)) {
      right = mid;     // Thử tốc độ chậm hơn
    } else {
      left = mid + 1;  // Cần tốc độ nhanh hơn
    }
  }
 
  return left;
}
 
function canFinish(piles: number[], speed: number, hours: number): boolean {
  let totalHours = 0;
  for (const pile of piles) {
    totalHours += Math.ceil(pile / speed);
  }
  return totalHours <= hours;
}
 
console.log(minEatingSpeed([3, 6, 7, 11], 8));   // 4
console.log(minEatingSpeed([30, 11, 23, 4, 20], 5)); // 30
console.log(minEatingSpeed([30, 11, 23, 4, 20], 6)); // 23

# Python - Koko Eating Bananas
import math
 
def min_eating_speed(piles: list[int], h: int) -> int:
    left, right = 1, max(piles)
 
    while left < right:
        mid = left + (right - left) // 2
 
        if can_finish(piles, mid, h):
            right = mid      # Thử tốc độ chậm hơn
        else:
            left = mid + 1   # Cần tốc độ nhanh hơn
 
    return left
 
def can_finish(piles: list[int], speed: int, hours: int) -> bool:
    total_hours = sum(math.ceil(pile / speed) for pile in piles)
    return total_hours <= hours
 
print(min_eating_speed([3, 6, 7, 11], 8))    # 4
print(min_eating_speed([30, 11, 23, 4, 20], 5))  # 30

Search space: [1, 11]
 
mid=6: ceil(3/6)+ceil(6/6)+ceil(7/6)+ceil(11/6) = 1+1+2+2 = 6 ≤ 8 ✓ → right=6
mid=3: ceil(3/3)+ceil(6/3)+ceil(7/3)+ceil(11/3) = 1+2+3+4 = 10 > 8 ✗ → left=4
mid=5: ceil(3/5)+ceil(6/5)+ceil(7/5)+ceil(11/5) = 1+2+2+3 = 8 ≤ 8 ✓ → right=5
mid=4: ceil(3/4)+ceil(6/4)+ceil(7/4)+ceil(11/4) = 1+2+2+3 = 8 ≤ 8 ✓ → right=4
 
left=4, right=4 → return 4