modyfikacja wyszukiwania binarnego

Czesc,
mam napisac algorytm dla takiego zadania:
mamy 2 tablice (n elementowe ) o krorych wiemy ze tablica A ma coraz wieksze roznicee miedzy 2 kolejnymi elementami, tablica B ma coraz mniejsze różnice. Chcemy znaleźć takie i dla ktorego A[i]==B[i].
i jescze mamy 2 "podzadania" tzn
a) tablice sa scisle rosnące
b) tablice sa dowolne
co do zadania b to widac ze sa to TAK JAKBY 2 funkcje kwadratowe. A w zadaniu a to też tak jakby kwadratowe tylko rozpatrujemy tylko ten fragment gdzie jedna rosnie a druga maleje czyli tak jakby tylko polowe funkcji.
Mam nadzieje że w miare jasno opisałem problem. Czy macie jakies pomysły? Rozwiazanie oczywiste czyli to o złozonosci n oczywiscie nie wystarczy.
Do zadania bedzie trzeba uzyc jakiejs modyfikacji binary serch. (bardzo mozliwe ze 2 razy bo takich punktow moze być 2). Czy macie jakies pomysly / podpowiedzi?
Dzieki za kazda odpowiedz.

widac ze sa to TAK JAKBY 2 funkcje kwadratowe.

Co to są funkcje tak jakby kwadratowe?

a to też tak jakby kwadratowe tylko rozpatrujemy tylko ten fragment gdzie jedna rosnie a druga maleje czyli tak jakby tylko polowe funkcji.

??

Patryk27 napisał(a):

widac ze sa to TAK JAKBY 2 funkcje kwadratowe.

Co to są funkcje tak jakby kwadratowe?

a to też tak jakby kwadratowe tylko rozpatrujemy tylko ten fragment gdzie jedna rosnie a druga maleje czyli tak jakby tylko polowe funkcji.

??

chodziło mi o to że w BARDZO DUZYM uproszczeniu sa jak f kwadratowe, dlatego że tak jak w f. kwadratowej pochodna to funkcja liniowa, to tutaj mamy cos podobnego bo w zadaniu różnice miedzy dwoma elementami są coraz wieksze czyli pochodna tez jest w UPOSZCZENIU prosta.
Oczywiscie, są to uproszczenia i oczywiscie to nie sa funkcje kwadratowe ani troche. Ale wydaje mi się że zauważenie takiego podobieństwa może pomoc w rozwiazaniu zadania.

Określenie którego szukasz, to funkcja wklęsła/wypukła…

W a masz zwykłe wyszukiwanie binarne.
W b wyznacz punkty przegięcia w tablicach (czyli gdzie różnica zmienia znak) i potem rozpatrz kilka podprzedziałów.

To co, może dyskretna wersja metody Newtona, dla dzielonych różnic, a nie pochodnych?