| 1 | // interpolation_search.rs |
| 2 | |
| 3 | fn interpolation_search(nums: &[i32], target: i32) -> bool { |
| 4 | if nums.is_empty() { return false; } |
| 5 | |
| 6 | let mut high = nums.len() - 1; |
| 7 | let mut low = 0usize; |
| 8 | loop { |
| 9 | let low_val = nums[low]; |
| 10 | let high_val = nums[high]; |
| 11 | if high <= low || target < low_val || target > high_val { |
| 12 | break; |
| 13 | } |
| 14 | |
| 15 | // 计算插值位置 |
| 16 | let offset = (target - low_val)*(high - low) as i32 / (high_val - low_val); |
| 17 | let interpolant = low + offset as usize; |
| 18 | |
| 19 | // 更新上下界 high、low |
| 20 | if nums[interpolant] > target { |
| 21 | high = interpolant - 1; |
| 22 | } else if nums[interpolant] < target { |
| 23 | low = interpolant + 1; |
| 24 | } else { |
| 25 | break; |
| 26 | } |
| 27 | } |
| 28 | |
| 29 | // 判断最终确定的上界处是否是 target |
| 30 | if target == nums[high] { |
| 31 | true |
| 32 | } else { |
| 33 | false |
| 34 | } |
| 35 | } |
| 36 | |
| 37 | fn main() { |
| 38 | let nums = [1,9,10,15,16,17,19,23,27,28,29,30,32,35]; |