資訊專欄INFORMATION COLUMN
摘要：基本思想二分查找算法的基本思想就是在一個(gè)有序的默認(rèn)我們都是升序，如果是降序后面的條件置反即可數(shù)組中將要查找的值和數(shù)組中間的那個(gè)元素比較如果要找的數(shù)大于中間的元素就從中間的元素后一個(gè)元素開始到數(shù)組最后一個(gè)元素這個(gè)區(qū)間里面繼續(xù)尋找如果要找的數(shù)小
基本思想
二分查找算法的基本思想就是:
在一個(gè)有序的(默認(rèn)我們都是升序，如果是降序后面的條件置反即可)數(shù)組中;
將要查找的值和數(shù)組中間的那個(gè)元素比較;
如果要找的數(shù)大于中間的元素,就從中間的元素后一個(gè)元素開始到數(shù)組最后一個(gè)元素這個(gè)區(qū)間里面繼續(xù)尋找;
如果要找的數(shù)小于中間的元素,就從0開始到此時(shí)的中間的元素這個(gè)區(qū)間內(nèi)繼續(xù)尋找;
如果它們相等，那么此時(shí)我們要找的元素就是當(dāng)前中間的元素，直接返回下標(biāo)即可。
java代碼實(shí)現(xiàn)
private int binarySearch(int[] arr,int k){
int index = -1;
int start = 0;
int end = arr.length;
while (start < end){
// 這里有可能會(huì)溢出，有兩種解決方案
// 1、 修改為 start+(end-start)/2
// 2、 通過(guò)位移操作，這樣也可以完成除2，在jdk源碼中使用的是這種方法
int mid = (end + start) / 2;
// 如果小于中間的元素就從0開始到當(dāng)前中間的下標(biāo)這個(gè)區(qū)間里面繼續(xù)尋找
if (k < arr[mid]){
end = mid;
// 如果大于中間的元素就從當(dāng)前的下標(biāo)到最后一個(gè)元素這個(gè)區(qū)間里面繼續(xù)尋找
}else if (k > arr[mid]){
start = mid + 1;
// 如果等于中間的元素就說(shuō)明當(dāng)前元素就是我們要找的下標(biāo)
}else {
return mid;
}
}
// 如果循環(huán)結(jié)束了都沒(méi)找到說(shuō)明這個(gè)數(shù)組里面沒(méi)有我們要找的元素
return -1;
}
時(shí)間復(fù)雜度分析
最好的情況是我們要找的就是中間那個(gè),此時(shí)的時(shí)間復(fù)雜度為O(1);
最壞的情況是我們找完最后一趟才找到甚至沒(méi)有找到,這個(gè)時(shí)候的時(shí)間復(fù)雜度為O(logN);
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/72094.html
摘要：為檢查長(zhǎng)度為的列表，二分查找需要執(zhí)行次操作。最后需要指出的一點(diǎn)是高水平的讀者可研究一下二叉樹關(guān)于二叉樹，戳這里數(shù)據(jù)結(jié)構(gòu)與算法二叉樹算法常見練習(xí)在一個(gè)二維數(shù)組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。 常見數(shù)據(jù)結(jié)構(gòu) 簡(jiǎn)單數(shù)據(jù)結(jié)構(gòu)（必須理解和掌握） 有序數(shù)據(jù)結(jié)構(gòu)：棧、隊(duì)列、鏈表。有序數(shù)據(jù)結(jié)構(gòu)省空間（儲(chǔ)存空間?。?無(wú)序數(shù)據(jù)結(jié)構(gòu)：集合、字典、散列表，無(wú)序...
摘要：為檢查長(zhǎng)度為的列表，二分查找需要執(zhí)行次操作。最后需要指出的一點(diǎn)是高水平的讀者可研究一下二叉樹關(guān)于二叉樹，戳這里數(shù)據(jù)結(jié)構(gòu)與算法二叉樹算法常見練習(xí)在一個(gè)二維數(shù)組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。 常見數(shù)據(jù)結(jié)構(gòu) 簡(jiǎn)單數(shù)據(jù)結(jié)構(gòu)（必須理解和掌握） 有序數(shù)據(jù)結(jié)構(gòu)：棧、隊(duì)列、鏈表。有序數(shù)據(jù)結(jié)構(gòu)省空間（儲(chǔ)存空間?。?無(wú)序數(shù)據(jù)結(jié)構(gòu)：集合、字典、散列表，無(wú)序...
摘要：為檢查長(zhǎng)度為的列表，二分查找需要執(zhí)行次操作。最后需要指出的一點(diǎn)是高水平的讀者可研究一下二叉樹關(guān)于二叉樹，戳這里數(shù)據(jù)結(jié)構(gòu)與算法二叉樹算法常見練習(xí)在一個(gè)二維數(shù)組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。 常見數(shù)據(jù)結(jié)構(gòu) 簡(jiǎn)單數(shù)據(jù)結(jié)構(gòu)（必須理解和掌握） 有序數(shù)據(jù)結(jié)構(gòu)：棧、隊(duì)列、鏈表。有序數(shù)據(jù)結(jié)構(gòu)省空間（儲(chǔ)存空間?。?無(wú)序數(shù)據(jù)結(jié)構(gòu)：集合、字典、散列表，無(wú)序...
摘要：遞歸實(shí)現(xiàn)不考慮相同數(shù)二分查找，不考慮有相同數(shù)的情況遞歸找到了考慮有相同數(shù)二分查找考慮有相同元素的情況遞歸要查找的值 1.遞歸實(shí)現(xiàn) ①不考慮相同數(shù) /** * 二分查...
摘要：查找算法之二分查找法思想二分查找法的思想非常簡(jiǎn)單，對(duì)于一個(gè)有序數(shù)列，找它中間的元素，看是否是查找目標(biāo)，如果不是，就看這個(gè)查找目標(biāo)是小于還是大于中間元素，然后在對(duì)應(yīng)的區(qū)間內(nèi)重復(fù)上述過(guò)程。 查找算法之二分查找法 思想 二分查找法的思想非常簡(jiǎn)單，對(duì)于一個(gè)有序數(shù)列，找它中間的元素，看是否是查找目標(biāo)，如果不是，就看這個(gè)查找目標(biāo)是小于還是大于中間元素，然后在對(duì)應(yīng)的區(qū)間內(nèi)重復(fù)上述過(guò)程。 算法 需要注...
閱讀 808·2021-10-14 09:43
閱讀 2133·2021-09-30 09:48
閱讀 3456·2021-09-08 09:45
閱讀 1103·2021-09-02 15:41
閱讀 1898·2021-08-26 14:15
閱讀 786·2021-08-03 14:04
閱讀 2985·2019-08-30 15:56
閱讀 3080·2019-08-30 15:52
