peak finding

本文最后更新于:August 1, 2020 pm

Peak finding

Recently i have learned MIT 6006 lesson.The first lesson introduced how to use divide and conquer to solve the peak finding problem.I will record my implementation of peaking finding by C++ here.

Definition

Element which is bigger than its adjacent elements is a peak

Proof of existing a peek(for 1D and 2D matrix,use the mathematical induction)

1D

when $n=1$,it is true and $a[0]$ itself is peek.

Suppose when $n=k$ it is true,which means an array of length k has at least one peek

$$
\begin{pmatrix}
a_0&& a_1 && a_2&&\cdots && a_k \\
\end{pmatrix}
$$

Then it comes to $n=k+1$ we append an element to the array and it comes to two cases

  • the peak of origin array is $a[k-2]$
  • the peak of origin array is not $a[k-2]$

for the first situation,either $a[k-1]$ or $a[k-2]$ is a peek because if the new-added element$>a[k-2]$ then it is a peek.Otherwise,$a[k-2]$ still remains to be a peek.

For the second situation,appending an element won’t interfere with the existence of the original peek.Thus,we have proved it

2D

Since the 2D matrix have a max value,the max element itself is the peek

algorithm to find the peak

Situation for 1D

Suppose you have an array

$$
\begin{pmatrix}
a_0&& a_1 && a_2&&\cdots && a_n \\
\end{pmatrix}
$$

$$
\begin{cases}
return\ a[0:\frac{n}{2}-1 ] & a[\frac{n}{2}] < a[\frac{n}{2}-1]\\
return\ a[\frac{n}{2}+1:n ] & a[\frac{n}{2}] < a[\frac{n}{2}+1]\\
return\ a[\frac{n}{2}] & a[\frac{n}{2}] \geq a[\frac{n}{2}+1]\ and\ a[\frac{n}{2}] \geq a[\frac{n}{2}-1]
\end{cases}
$$

because if $a[\frac{n}{2}]$ is smaller than its neighbors,it can’t be a peak.Thus,the bigger part must have a peak.(use proof by contradiction,if no peak,than a[1]>a[0],a[2]>a[1]…then $a[\frac{n}{2}-1 ]$ can’t bigger than the middle.)

Code for 1D

template<typename T>
T peak1D(const std::vector<T>& para,int begin,int end) {
	if (begin == end)return para[begin];
	if (begin == end - 1)return std::max({ para[begin],para[end] });//to ensure there is at least 3 elements
	int center = (begin + end) / 2;
	if (para[center - 1] > para[center])return peak1D(para, begin, center - 1);
	if (para[center + 1] > para[center])return peak1D(para, center + 1, end);
	return para[center];
}
template<typename T>
int peak1D(const std::vector<T>& para) {
	return peak1D(para, 0, para.size() - 1);
}

It is a simple divide and conquer example,and we analyse the complexity,the recurrence equation is as followed.

$T(n)=T(\frac{n}{2})+O(1)$
and the complexity is $\log_2N$

Situation for 2D

Suppose you have an array

$$
\begin{pmatrix}
a_{00}&& a_{01} && a_{02}&&\cdots && a_{0n} \\
a_{10}&& a_{11} && a_{12}&&\cdots && a_{1n}\\
\vdots && \vdots && \vdots && \ddots && \vdots \\
a_{m0}&& a_{m1} && a_{m2}&&\cdots && a_{mn} \\
\end{pmatrix}
$$

First you select the middle row and find the biggest element.We represent the index of the biggest element as max_index
$$
\begin{cases}
return\ a[0:\frac{m}{2}-1 ][0:n] & a[\frac{m}{2}][max\_index] < a[\frac{n}{2}-1][max\_index]\\
return\ a[\frac{m}{2}+1:m ][0:n] & a[\frac{m}{2}][max\_index] < a[\frac{n}{2}+1][max\_index]\\
return\ a[\frac{m}{2}][max\_index] & a[\frac{m}{2}] \geq a[\frac{m}{2}+1][max\_index]\ and\\a[\frac{m}{2}][max\_index] \geq a[\frac{m}{2}-1][max\_index]
\end{cases}
$$

the essence of this idea is similar to the 1D one and you can imagine compress the 2D matrix into an 1D array and use the max element to instead the whole row and it becomes to a 1D problem.You could also use prove that the $a[0:\frac{m}{2}-1 ][0:n]$ or the $a[\frac{m}{2}+1:m ][0:n]$ must have a peek,(because $a[0:\frac{m}{2}-1 ][max\_index]$ become a lower edge and the initial edge is a lower edge so there must exist a peek. it quite like the fermat theorem in calculus)

Code for 2D

template<typename T>
T peak2D(const vector<vector<T>>& para,int beginrow,int endrow,int col) {
	if (endrow - beginrow == 0)return *std::max_element(para[beginrow].begin(), para[beginrow].end());
	if (endrow - beginrow == 1)return std::max(*std::max_element(para[beginrow].begin(),para[beginrow].end()), *std::max_element(para[endrow].begin(), para[endrow].end()));
	int max_index = std::max_element(para[(endrow+beginrow)/ 2].begin(), para[(endrow + beginrow) / 2].end()) - para[(endrow + beginrow) / 2].begin();
	if (para[(endrow + beginrow) / 2][max_index] < para[(endrow + beginrow) / 2 - 1][max_index]) return peak2D(para, beginrow, (endrow + beginrow) / 2 - 1, col);
	if (para[(endrow + beginrow) / 2][max_index] < para[(endrow + beginrow) / 2 + 1][max_index]) return peak2D(para, (endrow + beginrow) / 2 + 1, endrow, col);
	return para[(endrow + beginrow) / 2][max_index];
}
template<typename T>
T peak2D(const vector<vector<T>>& para) {
	return peak2D(para,0, para.size(), para[0].size());
}

the recurrence equation comes with
$T(m,n)=T(\frac{m}{2},n)+O(n)$ and the complexity is $n\log_2m$

Conclusion

Today i introduce the two algorithm with you and implement it with C++,hope it will help you