博客昵稱：吳NDIR
個(gè)人座右銘：得之淡然，失之坦然
作者簡介：喜歡輕音樂、象棋，愛好算法、刷題
其他推薦內(nèi)容：計(jì)算機(jī)導(dǎo)論速記思維導(dǎo)圖
其他內(nèi)容推薦：五種排序算法
在這個(gè)愉快的周末讓我們聊一下二分查找吧！二分查找是一種很常用的算法，可幫助我們在有序數(shù)組中快速查找元素。
概念
- 問題：想象一下，你有一堆按升序排列的數(shù)字，并且你需要在其中查找一個(gè)對應(yīng)的數(shù)字。
- 如果你采用線性查找方式，即從數(shù)組的首個(gè)元素開始遍歷，一直到找到對應(yīng)數(shù)字為止。
- 顯然，采用這種方法你可能需要遍歷整個(gè)數(shù)組。如果數(shù)組很大，則這種線性查找方式會變得很慢。讓我們看看二分查找吧！
- 當(dāng)我們需要在一個(gè)有序數(shù)組中查找某個(gè)值的位置時(shí)，二分查找是一個(gè)高效的算法。這個(gè)算法的核心思想是將數(shù)組一分為二，然后判斷目標(biāo)值可能存在于數(shù)組的哪一個(gè)半邊，不斷縮小范圍，最終找到目標(biāo)位置或者確定目標(biāo)值不存在于數(shù)組中。
下面是二分查找的一般步驟：
-
首先確定目標(biāo)值在數(shù)組的哪個(gè)區(qū)間內(nèi)。將目標(biāo)值和數(shù)組的中間值進(jìn)行比較，如果目標(biāo)值等于中間值，那么我們已經(jīng)找到了目標(biāo)，在中間值的位置返回。如果目標(biāo)值小于中間值，那么我們將在左半邊查找目標(biāo)，否則我們將在右半邊查找目標(biāo)。
-
分別使用上一步中的方式在左半邊或右半邊遞歸查找，直到找到目標(biāo)或者確定目標(biāo)不存在于數(shù)組中。
-
如果我們發(fā)現(xiàn)要查找的目標(biāo)值不在數(shù)組中，那么我們可以返回 -1 表示未找到目標(biāo)。
二分查找的時(shí)間復(fù)雜度為 O(log n)，其中 n 表示數(shù)組長度。這是因?yàn)槊看伪容^可以將查找范圍減半，而在最壞情況下需要進(jìn)行的比較次數(shù)是 log n。在使用二分查找時(shí)，需要注意一些細(xì)節(jié)，首先數(shù)組必須是已經(jīng)排序好的，查找范圍的左右邊界需要正確設(shè)置，一些邊界條件需要特殊處理等。同時(shí)，二分查找并不適用于所有場景，例如數(shù)據(jù)量很小時(shí)使用暴力搜索會更加有效。
引例
現(xiàn)在讓我們看看一道有關(guān)二分查找的題目吧!
題目描述：
- 給定一個(gè) n 個(gè)元素有序的（升序）整型數(shù)組 nums 和一個(gè)目標(biāo)值 target ，寫一個(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
-
思路步驟
1.首先將數(shù)組分為左右兩個(gè)區(qū)間
2.將中間數(shù)與待查找目標(biāo)比較
- 在查找范圍區(qū)間[left, right]中取中點(diǎn) mid，比較 nums[mid] 和 target 的大小。
如果 nums[mid] = target，則mid即為要尋找的下標(biāo)，返回 mid。
如果 nums[mid] < target，則target只可能在mid的右側(cè)，更新區(qū)間[mid+1,right]。
如果 nums[mid] > target，則target只可能在mid的左側(cè)，更新區(qū)間[left,mid-1]。
3.重復(fù)步驟1和2，直到找到目標(biāo)target或者未找到目標(biāo)但left=right
4.最終返回下標(biāo)，或返回-1表示 target 不存在于 nums 數(shù)組中。
文章來源：http://www.zghlxwxcb.cn/news/detail-417345.html
- 示例代碼
int search(int nums[], int numsSize, int target){
int left=0,right=numsSize-1，mid;
while(left<=right){
mid=left+(right-left)/2;//根據(jù)新區(qū)間定義中間數(shù)下標(biāo)
//比較判斷
if(nums[mid]<target){
left=mid+1;//定義區(qū)間[mid+1,right]
}
else if(nums[mid]>target){
right=mid-1;//定義區(qū)間[left,mid-1]
}
else{
return mid;//找到target并返回下標(biāo)
}
}
return -1;//未找到返回-1
}
講解
- 在上述代碼中，我們首先初始化左右兩個(gè)指針。**left 和 right 分別指向數(shù)組的第一位和最后一位。**然后，我們在循環(huán)中計(jì)算中間指針 mid 的位置，再將中間指針的值與要查找的值進(jìn)行比較，以確定在哪一側(cè)繼續(xù)搜索。如果找到匹配值，則返回其下標(biāo)；否則，如果整個(gè)數(shù)組都已搜索完畢，則返回 -1。
- 那么，我們要如何保證它的正確性和性能呢？
- 首先，我們需要確保我們的算法是正確的。在二分查找中，正確性在于確定中間元素是否是我們正在尋找的值，而不是中間位置是否已經(jīng)被檢查過。因此，我們可以通過在每個(gè)循環(huán)中將查找范圍的一半排除來保證其正確性。
- 其次，我們需要考慮性能問題。在最壞情況下，遍歷整個(gè)數(shù)組的時(shí)間復(fù)雜度為 O ( l o g n ) O(log n) O(logn)。但是，由于此算法可以輕松地丟棄一半的數(shù)據(jù)，因此在一些特殊情況下，我們可以獲得更快的執(zhí)行速度。
總而言之，二分查找是一種非常有效的算法，特別是在大型數(shù)據(jù)集上查找單個(gè)值時(shí)。通過理解二分查找算法的工作原理，我們可以更好地掌握它并將其用于實(shí)際開發(fā)中。文章來源地址http://www.zghlxwxcb.cn/news/detail-417345.html
到了這里，關(guān)于二分查找入門教學(xué)(動(dòng)態(tài)講解圖、模擬示例、二分查找代碼講解)的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
