數(shù)據(jù)結(jié)構(gòu)與算法學(xué)習(xí)(五)——神奇的二分法

二分法，以優(yōu)秀的復(fù)雜(log_2N)度成功的將順序查找拋在后面，成為我們最常用的算法。

在我們平常的認(rèn)知里，二分法只能用于解決有序的數(shù)據(jù)問題，但對(duì)于求解內(nèi)容的不同，它也可以用于無數(shù)的數(shù)據(jù)中，下面就有序數(shù)據(jù)和無序數(shù)據(jù)的相關(guān)問題進(jìn)行總結(jié)。

1. 二分法解決有序問題

1.1 查找某個(gè)數(shù)

1.2 大于等于某數(shù)最左側(cè)的位置

2. 二分法解決無序問題

2.1 局部最小值問題

首先來解釋一下什么是局部最小值：

  • 如果這個(gè)數(shù)在0位置：這個(gè)數(shù)小于1位置上的數(shù)；
  • 如果這個(gè)數(shù)在N位置：這個(gè)數(shù)小于N-1位置上的數(shù)；
  • 如果這個(gè)數(shù)在其他位置：這個(gè)數(shù)小于前一個(gè)位置上的數(shù)，還小于后一位位置上的數(shù)。

如果在一個(gè)無序數(shù)組中，相鄰兩數(shù)不相等，則從0 ~ (N-1)上存在局部最小值

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容