Search Insert Position

                                            
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return left;
    }
};

                                            
class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return left;
    }
}

                                            
class Solution(object):
    def searchInsert(self, nums, target):
        left, right = 0, len(nums) - 1
        
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        
        return left

                                            
int searchInsert(int* nums, int numsSize, int target) {
    int left = 0;
    int right = numsSize - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return left;
}

                                            
public class Solution {
    public int SearchInsert(int[] nums, int target) {
        int left = 0;
        int right = nums.Length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return left;
    }
}

                                            
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var searchInsert = function(nums, target) {
    let left = 0;
    let right = nums.length-1;

    while(left <= right){
        let mid = Math.floor((left+right) / 2);

        if(nums[mid] === target){
            return mid;
        }else if(nums[mid] < target){
            left = mid + 1;
        }else{
            right = mid - 1;
        }
    }

    return left;
};

                                            
function searchInsert(nums: number[], target: number): number {
    let left = 0;
    let right = nums.length - 1;

    while (left <= right) {
        let mid = Math.floor((left + right) / 2);

        if (nums[mid] === target) {
            return mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return left;
};

                                            
class Solution {
    /**
     * @param Integer[] $nums
     * @param Integer $target
     * @return Integer
     */
    function searchInsert($nums, $target) {
        $left = 0;
        $right = count($nums) - 1;
        
        while ($left <= $right) {
            $mid = $left + intval(($right - $left) / 2);
            
            if ($nums[$mid] == $target) {
                return $mid;
            } elseif ($nums[$mid] < $target) {
                $left = $mid + 1;
            } else {
                $right = $mid - 1;
            }
        }
        
        return $left;
    }
}

                                            
class Solution {
    func searchInsert(_ nums: [Int], _ target: Int) -> Int {
        var left = 0
        var right = nums.count - 1
        
        while left <= right {
            let mid = left + (right - left) / 2
            
            if nums[mid] == target {
                return mid
            } else if nums[mid] < target {
                left = mid + 1
            } else {
                right = mid - 1
            }
        }
        
        return left
    }
}

                                            
class Solution {
    fun searchInsert(nums: IntArray, target: Int): Int {
        var left = 0
        var right = nums.size - 1
        
        while (left <= right) {
            val mid = left + (right - left) / 2
            
            if (nums[mid] == target) {
                return mid
            } else if (nums[mid] < target) {
                left = mid + 1
            } else {
                right = mid - 1
            }
        }
        
        return left
    }
}

                                            
class Solution {
  int searchInsert(List<int> nums, int target) {
    int left = 0;
    int right = nums.length - 1;
    
    while (left <= right) {
      int mid = left + (right - left) ~/ 2;
      
      if (nums[mid] == target) {
        return mid;
      } else if (nums[mid] < target) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }
    
    return left;
  }
}

                                            
func searchInsert(nums []int, target int) int {
    left, right := 0, len(nums)-1
    for left <= right {
        mid := left + (right-left)/2
        if nums[mid] == target {
            return mid
        } else if nums[mid] < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return left
}

                                            
# @param {Integer[]} nums
# @param {Integer} target
# @return {Integer}
def search_insert(nums, target)
    left = 0
    right = nums.length - 1
    
    while left <= right
        mid = left + (right - left) / 2
        
        if nums[mid] == target
            return mid
        elsif nums[mid] < target
            left = mid + 1
        else
            right = mid - 1
        end
    end
    
    return left
end

                                            
object Solution {
    def searchInsert(nums: Array[Int], target: Int): Int = {
        var left = 0
        var right = nums.length - 1
        
        while (left <= right) {
            val mid = left + (right - left) / 2
            
            if (nums(mid) == target) {
                return mid
            } else if (nums(mid) < target) {
                left = mid + 1
            } else {
                right = mid - 1
            }
        }
        
        return left
    }
}

                                            
impl Solution {
    pub fn search_insert(nums: Vec<i32>, target: i32) -> i32 {
        match nums.binary_search(&target) {
            Ok(index) => index as i32,
            Err(index) => index as i32,
        }
    }
}

                                            
defmodule Solution do
  @spec search_insert(nums :: [integer], target :: integer) :: integer
  def search_insert(nums, target) do
    Enum.find_index(nums, &( &1 >= target )) || length(nums)
  end
end

To solve this coding challenge, let's break down the problem and understand the requirements and constraints in detail before moving into the pseudocode solution.

Explanation

The task is to find the position at which a target value should be inserted into a sorted array of distinct integers if it is not already present in the array. If the target is present, we should simply return its index. We are required to implement this with a time complexity of \(O(\log n)\), indicating the use of a binary search approach.

Problem Breakdown:

Input Description:

A sorted array
nums

of distinct integers.
An integer
target

.

Output Description:

The index if the target is found.
The index where the target would be inserted to maintain sorted order if the target is not found.

Constraints:

Array
nums

is sorted in ascending order.
Array
nums

contains distinct integers, so no duplicates are present.
Target and elements of the array are bounded by the range -10^4 to 10^4.
Array length ranges from 1 to 10^4.

Approach:

Given the requirement of \(O(\log n)\) time complexity, we will use a binary search algorithm. Binary search reduces the search range by half at each step, allowing us to efficiently find the target or the appropriate insertion position.

High-Level Steps:

Initialize two pointers,
left

and
right

, to the start (0) and end (length of the array - 1) of the array.
While the
left

pointer does not exceed the
right

pointer:

Calculate the middle index,
mid

.
Compare the
target

with the middle element
nums[mid]

:

If
nums[mid]

equals
target

, return
mid

.
If
target

is greater than
nums[mid]

, move the
left

pointer to
mid + 1

.
If
target

is less than
nums[mid]

, move the
right

pointer to
mid - 1

.

If the loop exits without finding the target, the
left

pointer will point to the insertion position where the target can be inserted in order.

Detailed Steps in Pseudocode:

                                            
function searchInsert(nums, target):
# Initialize pointers for the binary search
left = 0
right = length of nums - 1

# Binary search loop
while left <= right:
# Calculate the middle index
mid = left + (right - left) // 2

# Check if the middle element is the target
if nums[mid] == target:
return mid # Target found, return the index

# If target is greater than middle element, search in the right half
elif nums[mid] < target:
left = mid + 1

# If target is less than middle element, search in the left half
else:
right = mid - 1

# If we exit the loop, left is the insertion point
return left

Explanation of Pseudocode:

Initialization:

                                            
left = 0
right = length of nums - 1

left

and
right

variables are initialized to point to the first and last index of the array, respectively.

Binary Search Loop:

                                            
while left <= right:
mid = left + (right - left) // 2

This loop continues as long as
left

is less than or equal to
right

.
mid

is recalculated in each iteration to find the middle index of the current search range.

Comparison and Adjustment of Search Range:

                                            
if nums[mid] == target:
return mid

elif nums[mid] < target:
left = mid + 1

else:
right = mid - 1

If the middle element equals the target, return
mid

.
If the target is greater than the middle element, narrow the search to the right half by setting
left

to
mid + 1

.
If the target is less than the middle element, narrow the search to the left half by setting
right

to
mid - 1

.

Insertion Position:

                                            
return left

If the loop exits without finding the target,
left

will be the insertion point.

By following these steps, we ensure an \(O(\log n)\) time complexity while finding the target or determining its correct insertion position in the sorted array.