算法刷題筆記【數(shù)組】01
數(shù)組理論
數(shù)組是存放在連續(xù)內(nèi)存空間上的相同類(lèi)型數(shù)據(jù)的集合蒸走。
數(shù)組可以方便的通過(guò)下標(biāo)索引的方式獲取到下標(biāo)下對(duì)應(yīng)的數(shù)據(jù)。
注意
數(shù)組下標(biāo)都是從0開(kāi)始的捻艳。
數(shù)組內(nèi)存空間的地址是連續(xù)的
因?yàn)閿?shù)組的在內(nèi)存空間的地址是連續(xù)的驾窟，所以我們?cè)趧h除或者增添元素的時(shí)候，就難免要移動(dòng)其他元素的地址认轨。
數(shù)組例題
704.二分查找
題目：給定一個(gè) n 個(gè)元素有序的（升序）整型數(shù)組 nums 和一個(gè)目標(biāo)值 target 绅络，寫(xiě)一個(gè)函數(shù)搜索 nums 中的 target嘁字，如果目標(biāo)值存在返回下標(biāo)恩急，否則返回 -1。
示例 1:
輸入: nums = [-1,0,3,5,9,12], target = 9
輸出: 4
解釋: 9 出現(xiàn)在 nums 中并且下標(biāo)為 4
示例 2:
輸入: nums = [-1,0,3,5,9,12], target = 2
輸出: -1
解釋: 2 不存在 nums 中因此返回 -1
提示：
你可以假設(shè) nums 中的所有元素是不重復(fù)的纪蜒。
n 將在 [1, 10000]之間灭袁。
nums 的每個(gè)元素都將在 [-9999, 9999]之間举娩。
分析過(guò)程
【文字太長(zhǎng)不看系列：↓直接跳到末尾查看打印出循環(huán)過(guò)程的代碼便于理解】
循環(huán)不變量
區(qū)間定義后，每次改變區(qū)間后芙代，區(qū)間性質(zhì)不能變：保持 左閉右閉[a, b] / 左閉右開(kāi)[a, b)，處理規(guī)則要按照區(qū)間定義來(lái)寫(xiě)，使得每次操作的范圍劃分滿足區(qū)間的定義躏敢。
1.左閉右閉 [a, b]
while(left ?? right)
分析：如何判斷問(wèn)號(hào)處該使用小于(<)號(hào)還是小于等于(<=)號(hào)件余？
例如：當(dāng)下標(biāo)區(qū)間為[x,x]時(shí)讥脐，此時(shí)區(qū)間長(zhǎng)度為1，區(qū)間內(nèi)只有一個(gè)元素蛾扇。while判斷條件若使用"<="攘烛，則?left=nums[x]魏滚，right=nums[x]镀首，此時(shí)條件?left<=right?成立，能使得進(jìn)入循環(huán)的區(qū)間滿足循環(huán)不變鼠次；若使用"<"更哄，left=nums[x]芋齿，right=nums[x]，此時(shí)條件?left<right?不成立成翩，無(wú)法使進(jìn)入循環(huán)的區(qū)間滿足循環(huán)不變觅捆。
簡(jiǎn)單來(lái)看，閉區(qū)間麻敌，左邊界==右邊界是有意義的栅炒，因此判斷條件可以寫(xiě)成?left <= right。
target < nums[mid] 時(shí)如何更新右邊界 right
分析：右邊界更新為 mid 還是 mid - 1术羔？
若目標(biāo)值小于二分后的中值赢赊，即?target < nums[mid]，則?nums[mid]?一定不在要查找的范圍內(nèi)级历，不可能為要查找的目標(biāo)值释移，即?target!=nums[mid]。此時(shí)更新右邊界值寥殖，right?的正確更新方式為?right = mid - 1玩讳，而非?right = mid，否則就將不屬于查找范圍中的值?nums[mid]?包含了進(jìn)來(lái)嚼贡。若錯(cuò)誤采用了?right < mid?寫(xiě)法熏纯，緊接下來(lái)的循環(huán)可能不會(huì)立即導(dǎo)致錯(cuò)誤，但當(dāng)程序運(yùn)行到二分區(qū)間只剩一個(gè)元素時(shí)粤策，很可能時(shí)本該被查到的目標(biāo)值因?yàn)椴粷M足?left < right?條件而退出循環(huán)豆巨，導(dǎo)致最終找不到目標(biāo)值。
target > nums[mid] 時(shí)如何更新左邊界 left
分析：左邊界更新為 mid 還是 mid - 1掐场？
由右邊界更新方式同理可知往扔，nums[mid]?不在區(qū)間中，左邊界更新只需?left = mid + 1?熊户。
2.左閉右開(kāi)[a, b)
while(left ?? right)
分析：如何判斷問(wèn)號(hào)處該使用小于(<)號(hào)還是小于等于(<=)號(hào)萍膛？
例如：當(dāng)下標(biāo)區(qū)間為[x,x)時(shí)，此時(shí)區(qū)間長(zhǎng)度為1嚷堡，區(qū)間內(nèi)只有一個(gè)元素蝗罗。while判斷條件若使用"<="，則表示可以有?left=nums[x]蝌戒，right=nums[x]串塑，此時(shí)條件?left<=right?，不能使得進(jìn)入循環(huán)的區(qū)間滿足循環(huán)不變北苟；若使用"<"桩匪，left=nums[x]，right=nums[x+1]友鼻，此時(shí)條件?left<right?成立傻昙，使進(jìn)入循環(huán)的區(qū)間滿足循環(huán)不變闺骚。
簡(jiǎn)單來(lái)看，閉區(qū)間妆档，**左邊界==右邊界 **是有意義的僻爽，因此判斷條件可以寫(xiě)成?left <= right。
target < nums[mid] 時(shí)如何更新右邊界 right
分析：右邊界更新為 mid 還是 mid - 1贾惦？
若目標(biāo)值小于二分后的中值胸梆，即?target < nums[mid]，則?nums[mid]?一定不在要查找的范圍內(nèi)须板，不可能為要查找的目標(biāo)值乳绕，即?target!=nums[mid]。此時(shí)更新右邊界值逼纸，right?可更新為?right = mid?洋措，表示取不到?mid?，而非?right = mid - 1杰刽，否則就將應(yīng)該屬于查找范圍中的值?nums[mid - 1]?剔除了菠发。
target > nums[mid] 時(shí)如何更新左邊界 left
分析：左邊界更新為 mid 還是 mid - 1？
由1中閉區(qū)間更新方式贺嫂，同理可知滓鸠，nums[mid]?不在區(qū)間中，左邊界更新仍為?left = mid + 1?第喳。
小結(jié)
將數(shù)組區(qū)間和數(shù)學(xué)數(shù)列中的區(qū)間聯(lián)系起來(lái)也很好理解糜俗。
左閉右閉方式，將一個(gè)完整區(qū)間分為3部分?（<t, =t, >t）曲饱，最終左右邊界會(huì)相等悠抹，指向最后一次查找的位置；
左閉右開(kāi)方式扩淀，將一個(gè)完整區(qū)間分為2部分?（<t, >=t）楔敌，該方式左右邊界不會(huì)有相等的情況，只會(huì)相鄰驻谆。
題解
算法刷題筆記【數(shù)組】01@蘭鐵二幼張同學(xué)-博客園
