1+ /**
2+ * File: binary_search.rs
3+ * Created Time: 2023-02-05
4+ * Author: sjinzh (sjinzh@gmail.com)
5+ */
6+
7+ /* 二分查找（双闭区间） */
8+ fn binary_search ( nums : & [ i32 ] , target : i32 ) -> i32 {
9+ // 初始化双闭区间 [0, n-1] ，即 i, j 分别指向数组首元素、尾元素
10+ let mut i = 0 ;
11+ let mut j = nums. len ( ) - 1 ;
12+ // 循环，当搜索区间为空时跳出（当 i > j 时为空）
13+ while i <= j {
14+ let m = ( i + j) / 2 ; // 计算中点索引 m
15+ if nums[ m] < target { // 此情况说明 target 在区间 [m+1, j] 中
16+ i = m + 1 ;
17+ } else if nums[ m] > target { // 此情况说明 target 在区间 [i, m-1] 中
18+ j = m - 1 ;
19+ } else { // 找到目标元素，返回其索引
20+ return m as i32 ;
21+ }
22+ }
23+ // 未找到目标元素，返回 -1
24+ return -1 ;
25+ }
26+
27+ /* 二分查找（左闭右开） */
28+ fn binary_search1 ( nums : & [ i32 ] , target : i32 ) -> i32 {
29+ // 初始化左闭右开 [0, n) ，即 i, j 分别指向数组首元素、尾元素+1
30+ let mut i = 0 ;
31+ let mut j = nums. len ( ) ;
32+ // 循环，当搜索区间为空时跳出（当 i = j 时为空）
33+ while i < j {
34+ let m = ( i + j) / 2 ; // 计算中点索引 m
35+ if nums[ m] < target { // 此情况说明 target 在区间 [m+1, j) 中
36+ i = m + 1 ;
37+ } else if nums[ m] > target { // 此情况说明 target 在区间 [i, m) 中
38+ j = m - 1 ;
39+ } else { // 找到目标元素，返回其索引
40+ return m as i32 ;
41+ }
42+ }
43+ // 未找到目标元素，返回 -1
44+ return -1 ;
45+ }
46+
47+ // Driver Code
48+ pub fn main ( ) {
49+ let target = 6 ;
50+ let nums = [ 1 , 3 , 6 , 8 , 12 , 15 , 23 , 67 , 70 , 92 ] ;
51+
52+ /* 二分查找（双闭区间） */
53+ let mut index = binary_search ( & nums, target) ;
54+ println ! ( "目标元素 6 的索引 = {index}" ) ;
55+
56+ /* 二分查找（左闭右开） */
57+ index = binary_search1 ( & nums, target) ;
58+ println ! ( "目标元素 6 的索引 = {index}" ) ;
59+ }
0 commit comments