| 1 | // binary_search.rs |
| 2 | |
| 3 | fn binary_search1(nums: &[i32], num: i32) -> bool { |
| 4 | let mut low = 0; |
| 5 | let mut high = nums.len() - 1; |
| 6 | let mut found = false; |
| 7 | |
| 8 | // 注意是 <= 不是 < |
| 9 | while low <= high && !found { |
| 10 | let mid: usize = (low + high) >> 1; |
| 11 | |
| 12 | // 若 low + high 可能溢出，可转换为减法 |
| 13 | // let mid: usize = low + ((high - low) >> 1); |
| 14 | |
| 15 | if num == nums[mid] { |
| 16 | found = true; |
| 17 | } else if num < nums[mid] { |
| 18 | high = mid - 1; // num < 中间值，省去后半部数据 |
| 19 | } else { |
| 20 | low = mid + 1; // num >= 中间值，省去前半部数据 |
| 21 | } |
| 22 | } |
| 23 | |
| 24 | found |
| 25 | } |
| 26 | |
| 27 | fn binary_search2(nums: &[i32], num: i32) -> bool { |
| 28 | // 基本情况1: 项不存在 |