美女,露乳鸡巴,亚洲国产精品日本,97国产日韩中文久久

algorithms.png

簡述: 從這篇文章起就會(huì)開啟另一個(gè)系列就是上篇文章中提到的每周學(xué)習(xí)一個(gè)基本算法，會(huì)結(jié)合LeetCode上題目來做分析。解題的語言一般是Kotlin或Java. 如果涉及到一些有關(guān)Kotlin的知識(shí)點(diǎn)也會(huì)做一些介紹。如果平時(shí)就養(yǎng)成學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)算法以及刷題的習(xí)慣，不管今后你是面試(愿從此再也不是面試造火箭平時(shí)擰螺絲了)或在實(shí)際上工作中都會(huì)對(duì)你有很大幫助。這也是這個(gè)系列文章的目的。

一、時(shí)間復(fù)雜度

最壞時(shí)間復(fù)雜度 O(log n)

最優(yōu)時(shí)間復(fù)雜度 O(1)

平均時(shí)間復(fù)雜度 O(log n)

二、基本思想

在一個(gè)有序的列表中，要查找的數(shù)與列表中間的位置相比，若相等說明找到了，若要查找的數(shù)大于列表中間的數(shù)，說明要查找的數(shù)可能在有序列表的后半部分；若要查找的數(shù)小于列表中間的數(shù)，說明要查找的數(shù)可能在有序列表的前半部分；然后類似上述操作縮短查找范圍，最后直到查找到最后一個(gè)數(shù)，如果不等于要查找的數(shù)，那么查找范圍就為空。

三、算法步驟

給定一個(gè)包含n個(gè)帶值的元素?cái)?shù)組或序列A[0], ... A[n-1]，使A[0] <= ... <= A[n-1]，以及目標(biāo)值Target.

1、令 low = 0, high = n - 1
2、若low > high, 則表示查找失敗結(jié)束
3、令mid(中間值元素)為 (low + high) / 2的值向下取整 (注意: 在具體實(shí)現(xiàn)中為了防止溢出，一般會(huì)采用 low + (high - low) / 2的值向下取整 或者直接采用位運(yùn)算的移位運(yùn)算來實(shí)現(xiàn)除2的操作。這個(gè)后面會(huì)有具體題目來說明)
4、若Target > A[mid], 令 low = mid + 1 (說明要查找的值在序列或數(shù)組后半部分(除去自身)，移動(dòng)low游標(biāo)，縮小查找范圍)，并回到步驟2
5、如果Target < A[mid], 令 high = mid - 1 (說明要查找的值在序列或數(shù)組前半部分(除去自身)，移動(dòng)high游標(biāo)，縮小查找范圍)，并回到步驟2
6、如果Target == A[mid], 查找成功并結(jié)束，返回mid下標(biāo)值。

四、算法過程演示

image

五、代碼實(shí)現(xiàn)(Kotlin語言描述)

二分查找算法主要有兩種實(shí)現(xiàn)方式，一種是循環(huán)遞推的方式，另一種則是遞歸的方式

1、 循環(huán)遞推實(shí)現(xiàn)方式

image
2、遞歸實(shí)現(xiàn)方式

image

六、為什么Java中mid = (low + high) / 2方式會(huì)溢出

相信刷過LeetCode題目的小伙伴們可能會(huì)在刷二分查找的題目過程會(huì)遇到超過時(shí)間限制的錯(cuò)誤

image

不知道大家有沒有去分析過為什么會(huì)得到超時(shí)啊，我都用了二分查找了時(shí)間復(fù)雜度都變成 O(log n) 呢，為啥還會(huì)超時(shí)呢。實(shí)際上是int數(shù)據(jù)類型溢出導(dǎo)致出現(xiàn)負(fù)數(shù)，使得代碼進(jìn)入了死循環(huán)，然后導(dǎo)致超時(shí)，最后OJ給你個(gè)超出時(shí)間錯(cuò)誤。

1、出現(xiàn)問題的原因

我們可以確定 low 和 high 都是非負(fù)數(shù)，那么也就是二進(jìn)制表示的最高位符號(hào)位是0，并且low 和 high 都是31位二進(jìn)制的整數(shù)

假設(shè)下面這種場(chǎng)景:

high = 0100 0000 0000 0000 0000 0000 0000 0000 = 1073741824 (Integer.MAX_VALUE的一半)
low  = 0100 0000 0000 0000 0000 0000 0000 0000 = 1073741824 (Integer.MAX_VALUE的一半)

當(dāng)執(zhí)行 low + high 操作時(shí)，進(jìn)行二進(jìn)制運(yùn)算，如下

high + low = 1000 0000 0000 0000 0000 0000 0000 0000

針對(duì)上述high + low 運(yùn)算的結(jié)果，如果是無符號(hào)的32位(4個(gè)字節(jié))Integer來說就表示 2147483648 (Integer.MAX_VALUE的大小)；如果是有符號(hào)的32位(4個(gè)字節(jié))Integer來說就表示 -2147483648。 需要特別注意的是Java或Kotlin中是不支持無符號(hào)的Integer類型，只存在有符號(hào)的Integer類型。

所以問題就來了，如果是在Java或Kotlin中 (low + high) / 2的值就變成了負(fù)數(shù) -1073741824，low = mid + 1, low就變成負(fù)數(shù)了。然后target的值會(huì)一直比mid要大 low就不斷累加，直到low又累加到1073741824，mid 又變成 -1073741824，不斷往復(fù)進(jìn)入了死循環(huán)導(dǎo)致超時(shí)?？梢钥聪旅孢@個(gè)例子:

image

運(yùn)算結(jié)果:

image

2、解決該問題的方式

針對(duì)上述問題，你可能看到兩種解決問題的辦法，一種是采用 low + (high - low) / 2，另一種就是 (low + high) >>> 1 或 Kotlin中的 (low + high) ushr 1.

(high + low) >>> 1 = 0100 0000 0000 0000 0000 0000 0000 0000 = 1073741824

一起來看下例子:

image

運(yùn)行結(jié)果:

image

七、補(bǔ)充一下Kotlin和Java中的位運(yùn)算的知識(shí)點(diǎn)

1、Java中的 >>> 與 >> (或Kotlin中的 ushr 與 shr ) 的區(qū)別

實(shí)際上無符號(hào)右移運(yùn)算符>>>(或kotlin中的ushr)和右移運(yùn)算符>>(或kotlin中的shr)是一樣的，只不過右移時(shí)左邊是補(bǔ)上符號(hào)位，而無符號(hào)右移運(yùn)算符是補(bǔ)上0

2、Kotlin中的位運(yùn)算

在Kotlin中拋棄了Java那種直接使用 >>>、>>、<<、&、~、|、^這些非語義化的符號(hào)來實(shí)現(xiàn)位運(yùn)算，說真的這樣符號(hào)對(duì)代碼可讀性確實(shí)降低了很多，看過源碼小伙伴就知道，很多源碼中為了追求代碼的運(yùn)行效率，往往會(huì)采用位運(yùn)算，但是代碼理解和讀起來就有點(diǎn)費(fèi)力了。然而很高興的是Kotlin卻采用一種更加語義化的中綴調(diào)用函數(shù)(infix)來實(shí)現(xiàn)位運(yùn)算，能夠做到真正的簡明識(shí)義, 并且用起來就像是在使用運(yùn)算符一樣，但是它更加具有含義。

image

八、LeetCode上二分查找相關(guān)的題目(練一練)

注意: 在做二分查找題目之前，給幾點(diǎn)建議。

1、真正在做題過程很少會(huì)有直接寫標(biāo)準(zhǔn)的二分查找的題目，一般都是需要變型，轉(zhuǎn)化成二分查找的問題。所以掌握二分查找思想比掌握實(shí)現(xiàn)方式更重要。

2、一般是二分查找去解題有個(gè)很明顯的特征那就是 升序數(shù)組或有序數(shù)組，以及在一些查找數(shù)中對(duì)時(shí)間復(fù)雜度要求比較高，比如時(shí)間復(fù)雜度必須低于O(n), 很明顯你不能直接用循環(huán)去做，二分查找的平均時(shí)間復(fù)雜度是O(log n) 明顯低于 O(n), 可能就需要你考慮是否能用二分查找。

3、還有一個(gè)典型使用二分查找的題目，就是求平方根或者求完全平方數(shù)，有個(gè)通用結(jié)論是: 一個(gè)非負(fù)數(shù)n的平方根小于n/2 + 1。所以就轉(zhuǎn)化了從[0,n/2 + 1]查找符合的平方根或完全平方數(shù)。