Easy 459. Closest Number in Sorted Array [Not exist in Leetcode]

Given a target number and an integer array A sorted in ascending order, find the index i in A such that A[i] is closest to the given target.

Return -1 if there is no element in the array.

Example

Given [1, 2, 3] and target = 2, return 1.

Given [1, 4, 6] and target = 3, return 1.

Given [1, 4, 6] and target = 5, return 1 or 2.

Given [1, 3, 3, 4] and target = 2, return 0 or 1 or 2. (三个答案得出任意一个都可)

Challenge

O(logn) time complexity.

Answer: ClosestNumber.cs

  public int SearchInsert(int[] nums, int target)
        {
            if (nums == null || nums.Length == 0) {
                return -1;
            }
            int currentIndex = FirstIndex(nums, target);

            if (currentIndex == 0) {
                return 0;
            }
            if (currentIndex == nums.Length -1){
                return nums.Length - 1;
            }

            if ((target - nums[currentIndex - 1]) < (nums[currentIndex] - target)) {
                return currentIndex - 1;
            }

            return currentIndex;
        }
        public int FirstIndex(int[] nums, int target) {
            int start = 0, end = nums.Length - 1;
            while (start + 1 < end)
            {
                int mid = start + (end - start) / 2;
                if (nums[mid] == target){
                    end = mid;
                }
                else if (nums[mid] < target){
                    start = mid;
                }
                else{
                    end = mid;
                }
            }
            if (nums[start] >= target) {
                return start;
            }
            if (nums[end] >= target)
            {
                return end;
            }
            return nums.Length -1;
        }