35. Search Insert Position Easy

1/**
2 * [35] Search Insert Position
3 *
4 * Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
5 * You must write an algorithm with O(log n) runtime complexity.
6 *  
7 * Example 1:
8 * 
9 * Input: nums = [1,3,5,6], target = 5
10 * Output: 2
11 * 
12 * Example 2:
13 * 
14 * Input: nums = [1,3,5,6], target = 2
15 * Output: 1
16 * 
17 * Example 3:
18 * 
19 * Input: nums = [1,3,5,6], target = 7
20 * Output: 4
21 * 
22 *  
23 * Constraints:
24 * 
25 * 1 <= nums.length <= 10^4
26 * -10^4 <= nums[i] <= 10^4
27 * nums contains distinct values sorted in ascending order.
28 * -10^4 <= target <= 10^4
29 * 
30 */
31pub struct Solution {}
32
33// problem: https://leetcode.com/problems/search-insert-position/
34// discuss: https://leetcode.com/problems/search-insert-position/discuss/?currentPage=1&orderBy=most_votes&query=
35
36// submission codes start here
37
38impl Solution {
39    pub fn search_insert(nums: Vec<i32>, target: i32) -> i32 {
40        let (mut start, mut end) = (0, nums.len() - 1);
41        while start <= end {
42            let mid = (end - start) / 2 + start;
43            if nums[mid] == target {
44                return mid as i32;
45            } else if nums[mid] > target {
46                if mid == 0 {
47                    return 0;
48                }
49                end = mid - 1;
50            } else {
51                start = mid + 1;
52            }
53        }
54        start as i32
55    }
56}
57
58// submission codes end
59
60#[cfg(test)]
61mod tests {
62    use super::*;
63
64    #[test]
65    fn test_35() {
66        assert_eq!(Solution::search_insert(vec![1,3,5,6], 5), 2);
67        assert_eq!(Solution::search_insert(vec![1,3,5,6], 2), 1);
68        assert_eq!(Solution::search_insert(vec![1,3,5,6], 7), 4);
69        assert_eq!(Solution::search_insert(vec![1,3], 7), 2);
70        assert_eq!(Solution::search_insert(vec![1,3], 2), 1);
71        assert_eq!(Solution::search_insert(vec![1,3], 0), 0);
72    }
73}
74