Problem $1$: Find Crossover Indices.

You are given data that consists of points $($x$0,$y$0),...,($xn$,$yn$)($x$0,$y$0),...,($xn$,$yn$),$ wherein x$0$xnyn$>$xn$.$

Find a "cross$-$over" index ii between $00$ and n$1$n$1$ such that yi$$xiyi$$xi and yi$+1>$xi$+1$yi$+1>$xi$+1.$

Note that such an index must always exist $($convince yourself of this fact before we proceed$).$

Example

ixiyi$002120242354467578681071012$i$01234567$xi$024567810$yi$2024781012$

Your algorithm must find the index i$=3$i$=3$ as the crossover point.

On the other hand, consider the data

ixiyi$002111\mathrm{.}5242354467578681071012$i$01234567$xi$014567810$yi$21\mathrm{.}524781012$

We have two cross over points. Your algorithm may output either i$=0$i$=0$ or i$=3$i$=3.$

$($A$)$ Design an algorithm to find an index i in $\{0,1,...,$n$1\}$i in $\{0,1,...,$n$1\}$ such that xi$$yixi$$yi but xi$+1$