今天來講二分跟內差搜尋法
又稱對數搜尋,如果搜尋的資料已經排好即可用二分搜尋法來進行搜尋。它是將資料分割成兩等份,再比較鍵值中間值大小,如果鍵值小於中間值,則可確定要找的資料是在前半段的元素,直到找到或確定不存在為止。
以此排序為例:
要搜尋11,先找到8/2=4,第四個元素為9。
第四個元素9比11小,所以捨棄第四個元素以前的元素。
對剩下的元素搜尋,4/2=2,4+2=6,取得第六個元素為12,比11還大,捨棄11以後的元素。
最後11=11,搜尋完成,如果不相等則表示找不到。
範例:
用二元搜尋法找出11:
fn main() {
let data = vec![2, 3, 5, 8, 9, 11, 12, 16, 18];
let target = 11;
let result = binary_search(&data, target);
match result {
Some(index) => println!("找到 {:?} 在第{:?}項.", target, index),
None => println!("{} 未找到.", target),
}
}
fn binary_search(data: &Vec<i32>, target: i32) -> Option<usize> {
let mut left = 0;
let mut right = data.len() - 1;
while left <= right {
let mid = left + (right - left) / 2;
if data[mid] == target {
return Some(mid);
}
if data[mid] < target {
left = mid + 1;
} else {
right = mid - 1;
}
}
None
}
內差搜尋又叫做差捕搜尋法,是二分法的改良版。是依照資料位置的分佈,利用公式來計算猜測搜尋鍵值的所在位置。
差值搜尋法和二元搜尋類似,不一樣在差值是每次從自訂的mid處開始搜尋。
他的公式是
mid = l + (h-l) * (key - data(h)) / data(h) - data(l))
key是要尋找的鍵,data(l)、data(h)是剩餘待尋找紀錄中最大與最小值,對資料筆數為n。
差補搜尋法步驟:
1.將紀錄由小到大順序給予1,2,3...n
2.另l=1,h=n
3.l < h時,重複執行步驟1和4
4.若key < key_mid且high != mid-1 則令h = mid-1
5.若key = key_mid表示成功搜尋到鍵值的位置
6.若key > key_mid且l != mid+1則令l = mid+1
範例:
用內差搜尋法找出11:
fn main() {
let data = vec![2, 3, 5, 8, 9, 11, 12, 16, 18];
let target = 17;
let result = interpolation_search(&data, target);
match result {
Some(index) => println!("找到 {} 在第 {} 項.", target, index),
None => println!("{} 未找到.", target),
}
}
fn interpolation_search(data: &Vec<i32>, target: i32) -> Option<usize> {
let mut left = 0;
let mut right = data.len() - 1;
while left <= right {
let range = data[right] as i32 - data[left] as i32;
if range == 0 {
if data[left] == target {
println!("目標 {} 等於左邊值 {},找到目標。", target, data[left]);
return Some(left);
} else {
println!("目標 {} 不等於左邊值 {},未找到目標。", target, data[left]);
return None;
}
}
// 計算位置
let mid = left + (((target - data[left]) * (right - left) as i32) / range) as usize;
if data[mid] == target {
println!("找到目標 {} 在第 {} 項。", target, mid);
return Some(mid);
} else if data[mid] < target {
println!("目標 {} 大於估計位置 {} 的值,向右搜索。", target, data[mid]);
left = mid + 1;
} else {
println!("目標 {} 小於估計位置 {} 的值,向左搜索。", target, data[mid]);
right = mid - 1;
}
}
println!("结束,沒找到。");
None
}
今天的內差法要理解公式的運行會比較好知道它的做法,只要記住他的公式就好處理相關問題。
目前應該不會太難吧🦑🦑!!
要是哪裡理解上還是邏輯上有錯請各位大大指正,感謝 🧙🧙🧙。