C# solution with comments


  • 0
    public class Solution {
        public int SearchInsert(int[] nums, int target) {
            return SearchInsert(nums, target, 0, nums.Length-1);
            
        }
        
        public int SearchInsert(int[] nums, int target, int low, int high)
        {
            if (low == high)
            {
                return (target > nums[low]) ? low + 1 : low;
            }
            
            while(low + 1 < high)
            {
                int mid = low + (high - low)/2;
                if (target < nums[mid] && target < nums[mid-1])
                {
                    high = mid -1;
                }
                else if (target > nums[mid] && target > nums[mid + 1])
                {
                    low = mid + 1;
                }
                else
                {
                    // Even though we know we know the number = mid, 
                    // we need to find the first position that this number starts at
                    high = mid;
                }
            }
            
            // Now there are just two elements pointed to by low and high
            if (target <= nums[low])
            {
                return low;
            }
            else if (target > nums[high])
            {
                return high + 1;
            }
            else {
                // Its in between these two elemets
                return low + 1;
            }
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.