description

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.

You must write an algorithm with O(log n) runtime complexity.

 

Example 1:

Input: nums = [1,3,5,6], target = 5
Output: 2

Example 2:

Input: nums = [1,3,5,6], target = 2
Output: 1

Example 3:

Input: nums = [1,3,5,6], target = 7
Output: 4

 

Constraints:

  • 1 <= nums.length <= 104
  • -104 <= nums[i] <= 104
  • nums contains distinct values sorted in ascending order.
  • -104 <= target <= 104

submission

impl Solution {
    // standard way to write a binary search use [left, right) range
    // thanks to the great Dijkstra
    // this can handle empty range, no exact match, multiple match
    // this is how it works
    // we define [left, right) is a range separate the whole range
    // into 3 parts
    // [0, left) => every number in this range is less than target
    // [left, right) => could either be less/equal/greater than target
    // [right, len) => greater or equal than target
    // our goal is to keep shrinking the [left, right) range until it
    // is empty. why? because 
    //  1. the origin range could be empty
    //  2. when it is empty, left == right, the origin range is essentially
    //     splitted into 2 parts with left/right also point to the start of
    //     the last range, which is what we want
    // Initially, we don't know anything, so left = 0, right = len
    // each step, we check the number in the mid of [left, right), if:
    //  nums[mid] < target: every number in [left, mid] is less than target
    //  nums[mid] >= target: every number in [mid, right) is greater or equal than target
    pub fn search_insert(nums: Vec<i32>, target: i32) -> i32 {
        // init condition
        let mut left = 0usize;
        let mut right = nums.len();
        // we want to shrink [left, right) to empty, so "<" is fine
        while left < right {
            // avoid integer overflow
            let mid = left + (right - left) / 2;
            // we want to split into lt/ge parts, so "<" here too
            if nums[mid] < target {
                // we know for sure nums[mid] is not target
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        left as _
    }
}