-
Notifications
You must be signed in to change notification settings - Fork 4
/
Copy pathmain.rs
119 lines (109 loc) · 4.58 KB
/
main.rs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
fn main() {
let x = Solution::search(vec![4,5,6,7,0,1,2,3], 3);
println!("x = {:#?}", x);
}
struct Solution {}
impl Solution {
pub fn search(nums: Vec<i32>, target: i32) -> i32 {
if nums.is_empty() { return -1 }
let mut s = 0;
let mut e = nums.len() - 1;
let mut m;
while s < e {
if e - s == 1 {
return
if nums[s] == target { s as i32 }
else if nums[e] == target { e as i32 }
else { -1 }
}
m = (s + e) / 2;
if nums[s] < nums[e] {
// sorted : binary search
if nums[m] < target { s = m }
else { e = m }
} else if nums[m] > nums[s] {
if nums[s] <= target && target <= nums[m] {
e = m
} else { s = m }
} else {
if nums[m] <= target && target <= nums[e] {
s = m;
} else { e = m }
}
}
if nums[s] != target { -1 } else { s as i32 }
}
}
#[cfg(test)]
mod test {
use crate::*;
#[test]
fn basic() {
assert_eq!(Solution::search(vec![4,5,6,7,0,1,2], 0), 4);
assert_eq!(Solution::search(vec![4,5,6,7,0,1,2], 3), -1);
}
#[test]
fn small() {
assert_eq!(Solution::search(vec![], 3), -1);
assert_eq!(Solution::search(vec![4], 3), -1);
assert_eq!(Solution::search(vec![4], 4), 0);
assert_eq!(Solution::search(vec![4], 5), -1);
assert_eq!(Solution::search(vec![1,2], 1), 0);
assert_eq!(Solution::search(vec![1,2], 2), 1);
assert_eq!(Solution::search(vec![1,2], 3), -1);
assert_eq!(Solution::search(vec![2,1], 1), 1);
assert_eq!(Solution::search(vec![2,1], 2), 0);
assert_eq!(Solution::search(vec![2,1], 3), -1);
assert_eq!(Solution::search(vec![1,2,3], 0), -1);
assert_eq!(Solution::search(vec![1,2,3], 1), 0);
assert_eq!(Solution::search(vec![1,2,3], 2), 1);
assert_eq!(Solution::search(vec![1,2,3], 3), 2);
assert_eq!(Solution::search(vec![1,2,3], 4), -1);
}
#[test]
fn even() {
assert_eq!(Solution::search(vec![4,5,6,7,0,1,2,3], 4), 0);
assert_eq!(Solution::search(vec![4,5,6,7,0,1,2,3], 5), 1);
assert_eq!(Solution::search(vec![4,5,6,7,0,1,2,3], 6), 2);
assert_eq!(Solution::search(vec![4,5,6,7,0,1,2,3], 7), 3);
assert_eq!(Solution::search(vec![4,5,6,7,0,1,2,3], 0), 4);
assert_eq!(Solution::search(vec![4,5,6,7,0,1,2,3], 1), 5);
assert_eq!(Solution::search(vec![4,5,6,7,0,1,2,3], 2), 6);
assert_eq!(Solution::search(vec![4,5,6,7,0,1,2,3], 3), 7);
}
#[test]
fn odd() {
assert_eq!(Solution::search(vec![4,6,7,0,1,2,3], 4), 0);
assert_eq!(Solution::search(vec![4,6,7,0,1,2,3], 5), -1);
assert_eq!(Solution::search(vec![4,6,7,0,1,2,3], 6), 1);
assert_eq!(Solution::search(vec![4,6,7,0,1,2,3], 7), 2);
assert_eq!(Solution::search(vec![4,6,7,0,1,2,3], 0), 3);
assert_eq!(Solution::search(vec![4,6,7,0,1,2,3], 1), 4);
assert_eq!(Solution::search(vec![4,6,7,0,1,2,3], 2), 5);
assert_eq!(Solution::search(vec![4,6,7,0,1,2,3], 3), 6);
}
#[test]
fn even_not_found() {
assert_eq!(Solution::search(vec![10,12,14,16,2,4,6,8], 1), -1);
assert_eq!(Solution::search(vec![10,12,14,16,2,4,6,8], 3), -1);
assert_eq!(Solution::search(vec![10,12,14,16,2,4,6,8], 5), -1);
assert_eq!(Solution::search(vec![10,12,14,16,2,4,6,8], 7), -1);
assert_eq!(Solution::search(vec![10,12,14,16,2,4,6,8], 9), -1);
assert_eq!(Solution::search(vec![10,12,14,16,2,4,6,8], 11), -1);
assert_eq!(Solution::search(vec![10,12,14,16,2,4,6,8], 13), -1);
assert_eq!(Solution::search(vec![10,12,14,16,2,4,6,8], 15), -1);
assert_eq!(Solution::search(vec![10,12,14,16,2,4,6,8], 17), -1);
}
#[test]
fn odd_not_found() {
assert_eq!(Solution::search(vec![10,12,16,2,4,6,8], 1), -1);
assert_eq!(Solution::search(vec![10,12,16,2,4,6,8], 3), -1);
assert_eq!(Solution::search(vec![10,12,16,2,4,6,8], 5), -1);
assert_eq!(Solution::search(vec![10,12,16,2,4,6,8], 7), -1);
assert_eq!(Solution::search(vec![10,12,16,2,4,6,8], 9), -1);
assert_eq!(Solution::search(vec![10,12,16,2,4,6,8], 11), -1);
assert_eq!(Solution::search(vec![10,12,16,2,4,6,8], 13), -1);
assert_eq!(Solution::search(vec![10,12,16,2,4,6,8], 15), -1);
assert_eq!(Solution::search(vec![10,12,16,2,4,6,8], 17), -1);
}
}