DEV Community

codingpineapple
codingpineapple

Posted on

LeetCode 35. Search Insert Position (javascript solution)

Description:

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.

You must write an algorithm with O(log n) runtime complexity.

Solution:

Time Complexity : O(log(n))
Space Complexity: O(1)

// Binary Search
var searchInsert = function(nums, target) {
    let left = 0, right = nums.length
    while(left < right) {
        const mid = left + Math.floor((right - left) / 2)
        if(nums[mid]===target) {
           return mid
        } else if(nums[mid] > target){
            right = mid
        } else {
            left = mid + 1
        }
    }
    return left
};
Enter fullscreen mode Exit fullscreen mode

Top comments (5)

Collapse
 
alaamahmoud__97 profile image
Alaa Abdelmotlep

I'm wondering about ' if(nums[mid]===target) { return mid } ' , statement return mid , But while loop won't loops after that In spite of we didn't break while loop ?

Collapse
 
pchelka84 profile image
Eveves

nums[mid]===target means that our target number exists in the given array and we only need to return its index. We don't need to do anything else after that.

Collapse
 
vishal590 profile image
vishal

On fourth line used const, how it works, cause we can't assign const variable and in this every time loop run const variable value changes.

Collapse
 
brownfrosamurai profile image
Meduna Oluwafemi

Since const mid is initialized in the while loop it gets created every time the loop runs a new iteration. The mid variable is not reassigned, only the left and right variables where reassigned .

Collapse
 
vishal590 profile image
vishal

why return left outside while loop without return left it gives correct answer