Question

Given a sorted array of distinct integers$\mathbf{A}\mathbf{[}\mathbf{1}\mathbf{,}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{,}\mathbf{n}\mathbf{]}$ , you want to find out whether there is an index$\mathit{i}$ for which $\mathbf{A}\mathbf{\left[}\mathbf{i}\mathbf{\right]}\mathbf{=}\mathbf{i}$. Give a divide-and-conquer algorithm that runs in time $\mathbf{O}\mathbf{\left(}\mathbf{log}\mathbf{n}\mathbf{\right)}$.

Short answer

By using binary search, only certain that there is no such value to the left of the middle element if $\mathrm{array}\left[\mathrm{mid}\right]<=\mathrm{start}\mathrm{index}$, where mid is index of middle element, and start index is the start of the array. A divide-and-conquer algorithm is constructed with run time $\mathrm{O}\left(\mathrm{logn}\right)$.

Step-by-step solution

Binary search algorithm and Divide-and-conquer algorithm.

Binary Search is used in a sorted array by repeatedly dividing the search interval in half. The idea of binary search is to use the information that the array is sorted and reduce the time complexity to$\mathrm{O}\left(\mathrm{logn}\right)$ .Binary Search also known as half-interval search, logarithmic search, or binary chop.Binary Search Algorithm can be implemented in the following two ways,

1.Iterative Method

2. Recursive Method

Sorting algorithm to be use in given situation

Use modification of binary search here :

Basically we have to find index such that $\mathrm{a}\left[\mathrm{i}\right]=\mathrm{i}\mathrm{in}\mathrm{other}\mathrm{a}\left[\mathrm{i}\right]-\mathrm{i}=0.$

Now as the array is sorted , so all the indices j which is less than i will satisfy the property

$:\mathrm{a}\left[\mathrm{j}\right]-\mathrm{j}<=0$

as the array is sorted so a[j] will be at least one less than a[i] and left index will also be at least one less than i hence the conclusion.

Similarly to the right of the last index element .

$\mathrm{a}\left[\mathrm{j}\right]-\mathrm{j}>=0.$

So the key idea is :

$\mathrm{mid}=\mathrm{left}+\mathrm{right}/2$where left and right are the boundary indices and then check whether mid is the last index ,index we are looking for using the above mentioned property.

For this we compare only its immediate left and right neighbours.

Given that the array is “SORTED”. We can more use of this property to improve the fine complexity to $\mathrm{O}\left(\log \mathrm{n}\right)$.

$-1$

$2$

$5$

$7$

$11$

$20$

$30$

Ex: $A$

Let’s say we to search “$20$” in our Array. First we go for middle element i.e.,$7$

Search if $7>20??$ False

If $7>20$teen we will only search on the right hand side of $7$.

Then, we have to search only in

11

20

30

Here, we are dividing the large problem into a sub-problem with less sited array.

$Mid=20$

Apply same procedure.

Here, we found the mid value as required $20$. This approach is called “Binary Search”

Algorithm

Algorithm $\mathrm{Binary}\mathrm{Search}(\mathrm{arr}\left[\right],\min ,\max ,\mathrm{key})$

{

If $(\max <\min )$then

Else return false.

$\mathrm{Mid}=(\max +\min )/2$

If $\mathrm{arr}\left[\mathrm{mid}\right]>\mathrm{key}$then

Return $\mathrm{Binary}\mathrm{Search}(\mathrm{arr},\min ,\mathrm{mid}-1,\mathrm{key})$

Else if $\mathrm{arr}\left[\mathrm{mid}\right]<\mathrm{key}$then

Return$\mathrm{Binary}\mathrm{Search}(\mathrm{arr},\mathrm{mid}+1,\max ,\mathrm{key})$

Else

Return

End if

End if

}

array[mid] <= start index

$\mathrm{p}[1\dots .\mathrm{n}]\mathrm{i}$s array of words frequencies of $\mathrm{size}‘\mathrm{n}’.$

$\begin{array}{l}\mathrm{for}(\mathrm{s}=1\mathrm{ton})\\ \begin{array}{l}\\ \mathrm{for}(\mathrm{i}=0\mathrm{ton}-\mathrm{s})\end{array}\\ \begin{array}{l}\\ \mathrm{j}=\mathrm{i}+\mathrm{s}\end{array}\\ \begin{array}{l}\\ \mathrm{if}(\mathrm{i}=\mathrm{j})\end{array}\end{array}$

$\begin{array}{l}\mathrm{T}(\mathrm{i},\mathrm{j})=\mathrm{p}\left[\mathrm{i}\right]\\ \begin{array}{l}\\ \mathrm{for}(\mathrm{k}=\mathrm{itoj}+1)\end{array}\\ \begin{array}{l}\\ \mathrm{T}(\mathrm{i},\mathrm{j})=\mathrm{T}(\mathrm{i},\mathrm{j})+\mathrm{p}\left[\mathrm{k}\right]\end{array}\\ \begin{array}{l}\\ \mathrm{returnT}(0,\mathrm{n}-1)\end{array}\end{array}$

This algorithm is constructed or take run time of $\mathrm{O}\left(\mathrm{logn}\right)$.

Here, the analysis of algorithm is given below, binary search, only certain that there is no such value to the left of the middle element ifrole="math" localid="1659776120568" $\mathrm{array}\left[\mathrm{mid}\right]<=\mathrm{start}\mathrm{index}$, where mid is index of middle element, and start index is the start of the array.And divide-and-conqueralgorithm is constructed with run time$O\left(\log n\right)$

Every fine we are dividing the array into half. i.e.,

If$n=100$, next call will be,

Call$n=50,25,12,6,3,1$base case.

We are performing $\mathrm{logn}$ operations.

Hence, time complexity: $O\left(logn\right)$