: Given a sorted array of distinct integers A$[1,...,$ n$],$ you want to find out whether there is an

index i for which A$[$i$]=$ i$.$ Give a divide$-$and$-$conquer algorithm that runs in time O$($log n$).$

$1$

Problem $4$: Given an array A$[1...$ n$]$ of n real numbers, give a divide$-$and$-$conquer style algorithm to

compute the number of distinct pairs, which are ordered pairs of indices $($i$,$ j$)$ such that i $<$ j and

A$[$i$]6=$ A$[$j$],$ in O$($n $$ log n$)$ time.

Example:

A $=[1,19,5,19]$

distinct pairs:$(1,2),(1,3),(1,4),(2,3),(3,4)$