Given a sorted array 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.

 Approach: Use binary search 

        public int SearchInsert(int[] nums, int target)

        {

            if (nums == null)

            {

                return -1;

            }

            if (nums.Length == 0 || target < nums[0])

            {

                return 0;

            }

            else if (target > nums[nums.Length - 1])

            {

                return nums.Length;

            }

            return this.SearchInsert(nums, 0, nums.Length - 1, target);

        }

        private int SearchInsert(int[] nums, int low, int high, int target)

        {

            if (low > high)

            {

                return -1;

            }

            int mid = (low + high) / 2;

            if (nums[mid] == target || (nums[mid] > target && nums[mid - 1] < target))

            {

                return mid;

            }

            else if (nums[mid] < target)

            {

                return this.SearchInsert(nums, mid + 1, high, target);

            }

            else

            {

                return this.SearchInsert(nums, low, mid - 1, target);

            }

        }