Closest pair sum in two sorted arrays
algorithm, arrays, c
Solution
Thinking a bit about it, then you could ask yourself: "Is it necessary, each time, to search in the sorted b-array for successive values from a[]?"
Problem
Given two sorted arrays of integers, `a` and `b`, and an integer `c`, I have to find `i,j` such that: ``` a[i] + b[j] <= c ``` and `a[i] + b[j]` is large as possible. The best solution I can think of is in O(nlogn) time, taking every integer from first array and finding the lower bound of "`c-a[i]`". Can anyone suggest me a better way to do this (maybe in O(n) time)?