Given two sorted lists of positive real values. L1 = {${x_1,x_2,...,x_n}$}, L1 is in Descending order L2 = {${y_1,y_2,...,y_n}$}, L2 is in Strictly ascending order
Now, we have a thrid list derived from L1 and L2, such that: L3 = {${x_1+y_1, x_2+y_2, ..., x_n+y_n}$}, L3 has the property of being bi-tonic (Decreasing and then Increasing).
Task:Need to find the index of the smallest value in L3. Constraint: One cannot perform a binary search (Iterating over lists from left to right, one step at a time), however the values at the extreme ends of L1 and L2 are known. Is it possible to avoid the evaluation of all the values of L3?
One Solution: 1) Solution is $i$: if the value at the $i^{th}$ index in L3 is smaller than $(i+1)^{th}$ value in the L2, as L2 is increasing strictly increasing. What are other properties that can be used to find the value of i?