Q1 :- Search Insert Position

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.

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

➡️ Solution

Approach

1. Initialize two pointers:

   • Create two variables, left and right, to represent the current search boundaries.
   • Set left = 0 and right = nums.length - 1.

2. Run a loop while left <= right:

   • This loop helps to narrow down the search space until the correct position is found.

3. Find the middle index:

   • Calculate mid = Math.floor((left + right) / 2) to get the midpoint of the current range.

4. Compare nums[mid] with target:

   • If nums[mid] === target: return mid (target found).
   • If nums[mid] < target: move the left pointer to mid + 1 (search right half).
   • Else: move the right pointer to mid - 1 (search left half).

5. Return left:

   • If the loop ends without finding the target, left will be at the position where the target should be inserted.

Complexity

• Time complexity: O(log n)
• Space complexity: O(1)

Code

 /** * @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 }; 

Q2 :- Sqrt(x)

Implement the function mySqrt(x) that computes and returns the integer part of the square root of a non-negative integer x.

• The returned integer should be the greatest integer r such that r * r <= x.
• Do not use any built-in exponent functions like Math.sqrt().

 Input: x = 8 Output: 2 Input: x = 4 Output: 2 

➡️ Solution

Approach

1. Handle Edge Case:

   • If x is 0, return 0 immediately since the square root of 0 is 0.

2. Initialize Search Range:

   • Set left = 0 and right = x. The square root of x will always lie within this range.

3. Binary Search Loop:

   • While left <= right:
     • Compute mid = Math.floor((left + right) / 2).
     • If mid * mid === x, return mid (exact square root found).
     • If mid * mid < x, move the left boundary to mid + 1 to search in the right half.
     • If mid * mid > x, move the right boundary to mid - 1 to search in the left half.

4. Return Result:

   • If the loop ends without finding an exact square root, return right, which will be the greatest integer r such that r * r <= x.

Time and Space Complexity

• Time Complexity: O(log x) — efficient due to binary search.
• Space Complexity: O(1) — constant space usage.

This method avoids using built-in functions and works efficiently even for large inputs.

Code

 /** * @param {number} x * @return {number} */ var mySqrt = function(x) { if (x === 0) return 0; let left = 0; let right = x while(left <= right){ let mid = Math.floor((left + right) / 2) if(mid * mid == x){ return mid }else if(mid * mid < x){ left = mid + 1 }else{ right = mid - 1 } } return right; };