algorithms.png

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

一赘方、時間復雜度

最壞時間復雜度 O(log n)

最優(yōu)時間復雜度 O(1)

平均時間復雜度 O(log n)

二烧颖、基本思想

在一個有序的列表中，要查找的數(shù)與列表中間的位置相比窄陡，若相等說明找到了炕淮，若要查找的數(shù)大于列表中間的數(shù)，說明要查找的數(shù)可能在有序列表的后半部分跳夭；若要查找的數(shù)小于列表中間的數(shù)涂圆，說明要查找的數(shù)可能在有序列表的前半部分；然后類似上述操作縮短查找范圍币叹，最后直到查找到最后一個數(shù)润歉，如果不等于要查找的數(shù)，那么查找范圍就為空颈抚。

三踩衩、算法步驟

給定一個包含n個帶值的元素數(shù)組或序列A[0], ... A[n-1]，使A[0] <= ... <= A[n-1]邪意，以及目標值Target.

• 1九妈、令 low = 0, high = n - 1
• 2反砌、若low > high, 則表示查找失敗結束
• 3雾鬼、令mid(中間值元素)為 (low + high) / 2的值向下取整 (注意: 在具體實現(xiàn)中為了防止溢出，一般會采用 low + (high - low) / 2的值向下取整 或者直接采用位運算的移位運算來實現(xiàn)除2的操作宴树。這個后面會有具體題目來說明)
• 4策菜、若Target > A[mid], 令 low = mid + 1 (說明要查找的值在序列或數(shù)組后半部分(除去自身)，移動low游標酒贬，縮小查找范圍)又憨，并回到步驟2
• 5、如果Target < A[mid], 令 high = mid - 1 (說明要查找的值在序列或數(shù)組前半部分(除去自身)锭吨，移動high游標蠢莺，縮小查找范圍)，并回到步驟2
• 6零如、如果Target == A[mid], 查找成功并結束躏将，返回mid下標值锄弱。

四、算法過程演示

image

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

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

• 1蚯窥、 循環(huán)遞推實現(xiàn)方式
  
  image
• 2掸鹅、遞歸實現(xiàn)方式
  
  image

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

相信刷過LeetCode題目的小伙伴們可能會在刷二分查找的題目過程會遇到超過時間限制的錯誤

image

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

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

假設下面這種場景:

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的一半)

當執(zhí)行 low + high 操作時敞临，進行二進制運算，如下

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

針對上述high + low 運算的結果麸澜，如果是無符號的32位(4個字節(jié))Integer來說就表示 2147483648 (Integer.MAX_VALUE的大小)挺尿；如果是有符號的32位(4個字節(jié))Integer來說就表示 -2147483648。 需要特別注意的是Java或Kotlin中是不支持無符號的Integer類型炊邦，只存在有符號的Integer類型编矾。

所以問題就來了，如果是在Java或Kotlin中 (low + high) / 2的值就變成了負數(shù) -1073741824馁害，low = mid + 1, low就變成負數(shù)了窄俏。然后target的值會一直比mid要大 low就不斷累加，直到low又累加到1073741824碘菜，mid 又變成 -1073741824凹蜈，不斷往復進入了死循環(huán)導致超時∪绦ィ可以看下面這個例子:

image

運算結果:

image

• 2仰坦、解決該問題的方式

針對上述問題，你可能看到兩種解決問題的辦法计雌，一種是采用 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

運行結果:

image

七、補充一下Kotlin和Java中的位運算的知識點

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

實際上無符號右移運算符>>>(或kotlin中的ushr)和右移運算符>>(或kotlin中的shr)是一樣的妈橄，只不過右移時左邊是補上符號位鼠渺，而無符號右移運算符是補上0

• 2、Kotlin中的位運算

在Kotlin中拋棄了Java那種直接使用 >>>眷细、>>拦盹、<<、&溪椎、~普舆、|、^這些非語義化的符號來實現(xiàn)位運算校读，說真的這樣符號對代碼可讀性確實降低了很多沼侣，看過源碼小伙伴就知道，很多源碼中為了追求代碼的運行效率歉秫，往往會采用位運算蛾洛，但是代碼理解和讀起來就有點費力了。然而很高興的是Kotlin卻采用一種更加語義化的中綴調(diào)用函數(shù)(infix)來實現(xiàn)位運算雁芙，能夠做到真正的簡明識義, 并且用起來就像是在使用運算符一樣轧膘，但是它更加具有含義。

image

八兔甘、LeetCode上二分查找相關的題目(練一練)

注意: 在做二分查找題目之前谎碍，給幾點建議。

• 1洞焙、真正在做題過程很少會有直接寫標準的二分查找的題目蟆淀，一般都是需要變型，轉(zhuǎn)化成二分查找的問題澡匪。所以掌握二分查找思想比掌握實現(xiàn)方式更重要熔任。
• 2、一般是二分查找去解題有個很明顯的特征那就是 升序數(shù)組或有序數(shù)組唁情，以及在一些查找數(shù)中對時間復雜度要求比較高疑苔，比如時間復雜度必須低于O(n), 很明顯你不能直接用循環(huán)去做，二分查找的平均時間復雜度是O(log n) 明顯低于 O(n), 可能就需要你考慮是否能用二分查找荠瘪。
• 3夯巷、還有一個典型使用二分查找的題目，就是求平方根或者求完全平方數(shù)哀墓，有個通用結論是: 一個非負數(shù)n的平方根小于n/2 + 1。所以就轉(zhuǎn)化了從[0,n/2 + 1]查找符合的平方根或完全平方數(shù)喷兼。

• 1篮绰、兩數(shù)之和 II - 輸入有序數(shù)組

  
  
  image
  
  
  image

• 2、有效的完全平方數(shù)

  
  
  image
  
  
  image

• 3季惯、x的平方根

  
  
  image
  
  
  image

• 4吠各、山脈數(shù)組的峰頂索引

  
  
  image
  
  
  image

• 5臀突、標準的二分查找

  
  
  image
  
  
  image
  
  
  image

• 6、尋找比目標字母大的最小字母

  
  
  image
  
  
  image

• 7贾漏、猜數(shù)字大小

  
  
  image
  
  
  image

• 8候学、第一個錯誤的版本

  
  
  image
  
  
  image

• 9、求兩個數(shù)組的交集

  
  
  image
  
  
  image

• 10纵散、兩個數(shù)組的交集 II

  
  
  image
  
  
  image

<div align="center"><img src="https://user-gold-cdn.xitu.io/2018/5/14/1635c3fb0ba21ec1?w=430&h=430&f=jpeg&s=39536" width="200" height="200"></div>

歡迎關注Kotlin開發(fā)者聯(lián)盟梳码，這里有最新Kotlin技術文章，每周會不定期翻譯一篇Kotlin國外技術文章伍掀。如果你也喜歡Kotlin掰茶，歡迎加入我們~~~

Kotlin系列文章，歡迎查看:

原創(chuàng)系列：

• 教你如何完全解析Kotlin中的類型系統(tǒng)
• 如何讓你的回調(diào)更具Kotlin風味
• Jetbrains開發(fā)者日見聞(三)之Kotlin1.3新特性(inline class篇)
• JetBrains開發(fā)者日見聞(二)之Kotlin1.3的新特性(Contract契約與協(xié)程篇)
• JetBrains開發(fā)者日見聞(一)之Kotlin/Native 嘗鮮篇
• 教你如何攻克Kotlin中泛型型變的難點(實踐篇)
• 教你如何攻克Kotlin中泛型型變的難點(下篇)
• 教你如何攻克Kotlin中泛型型變的難點(上篇)
• Kotlin的獨門秘籍Reified實化類型參數(shù)(下篇)
• 有關Kotlin屬性代理你需要知道的一切
• 淺談Kotlin中的Sequences源碼解析
• 淺談Kotlin中集合和函數(shù)式API完全解析-上篇
• 淺談Kotlin語法篇之lambda編譯成字節(jié)碼過程完全解析
• 淺談Kotlin語法篇之Lambda表達式完全解析
• 淺談Kotlin語法篇之擴展函數(shù)
• 淺談Kotlin語法篇之頂層函數(shù)蜜笤、中綴調(diào)用濒蒋、解構聲明
• 淺談Kotlin語法篇之如何讓函數(shù)更好地調(diào)用
• 淺談Kotlin語法篇之變量和常量
• 淺談Kotlin語法篇之基礎語法

Effective Kotlin翻譯系列

• [譯]Effective Kotlin系列之考慮使用原始類型的數(shù)組優(yōu)化性能(五)
• [譯]Effective Kotlin系列之使用Sequence來優(yōu)化集合的操作(四)
• [譯]Effective Kotlin系列之探索高階函數(shù)中inline修飾符(三)
• [譯]Effective Kotlin系列之遇到多個構造器參數(shù)要考慮使用構建器(二)
• [譯]Effective Kotlin系列之考慮使用靜態(tài)工廠方法替代構造器(一)

翻譯系列：

• [譯]記一次Kotlin官方文檔翻譯的PR(內(nèi)聯(lián)類)
• [譯]Kotlin中內(nèi)聯(lián)類的自動裝箱和高性能探索(二)
• [譯]Kotlin中內(nèi)聯(lián)類(inline class)完全解析(一)
• [譯]Kotlin的獨門秘籍Reified實化類型參數(shù)(上篇)
• [譯]Kotlin泛型中何時該用類型形參約束?
• [譯] 一個簡單方式教你記住Kotlin的形參和實參
• [譯]Kotlin中是應該定義函數(shù)還是定義屬性?
• [譯]如何在你的Kotlin代碼中移除所有的!!(非空斷言)
• [譯]掌握Kotlin中的標準庫函數(shù): run、with把兔、let沪伙、also和apply
• [譯]有關Kotlin類型別名(typealias)你需要知道的一切
• [譯]Kotlin中是應該使用序列(Sequences)還是集合(Lists)?
• [譯]Kotlin中的龜(List)兔(Sequence)賽跑

實戰(zhàn)系列:

• 用Kotlin擼一個圖片壓縮插件ImageSlimming-導學篇(一)
• 用Kotlin擼一個圖片壓縮插件-插件基礎篇(二)
• 用Kotlin擼一個圖片壓縮插件-實戰(zhàn)篇(三)
• 淺談Kotlin實戰(zhàn)篇之自定義View圖片圓角簡單應用