Applied Binary Search: Split Array Largest Sum

The concept of Naive Binary Search may appear straightforward, yet its proper comprehension often proves challenging. Additionally, the task of translating a given problem into a format suitable for binary search is far from intuitive. The crux of the matter lies in identifying an “ordering” pattern; once this is established, binary search can be effectively applied.

  1. Use
# Q-410: 27/jan/2023, binary search to find max sub-array sum in k splits
#
# About unit_used == k, it means already got one candidate "l"
#   if r = m will result in loop break, we still got the answer;
#   if r = m makes loop working still, we can safely check in next step
# @param {Integer[]} nums
# @param {Integer} k
# @return {Integer}
def split_array(nums, k)
  l, r = nums.max, nums.sum
  while l < r
    m = (l + r) / 2
    if unit_used(nums, m) > k # when we gain more units, means the unit_size is too small
      l = m + 1
    else # if already satisfied, or units count to less, we need to try smaller unit_size
      r = m
    end
  end
  l
end

# starts from 1 since at least one block will be used
def unit_used(nums, unit_size)
  sum = count = 0
  nums.each do |n|
    sum += n
    if sum > unit_size
      count += 1
      sum = n
    end
  end
  count + 1
end

p split_array([7, 2, 5, 10, 8], 2)
p unit_used([7, 2, 5, 10, 8], 18)
p split_array([1, 2, 3, 4, 5], 2)
p unit_used([1, 2, 3, 4, 5], 9)