Searching an Array, Two Ways

#javascript #codenewbie #leetcode #algorithms

Today's algorithm is the Search Insert Position problem:

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. You may assume no duplicates in the array.

For example, if the inputted array was [1, 2, 6, 8] and the target was 2, the function should return the output 1, because 2 is at the first index in the inputted array. If the inputted array was [1, 2, 6, 8] and the target was 4, the function should return the output 2, because in this ordered array, if we inserted 4 into it, it would be at index 2 (between numbers 2 and 6).

In this post, I'll discuss two ways to solve this problem. The first way is a single pass approach using a for loop, solved in O(n) time. The second way is a binary search approach, solved in O(log n) time.

Method #1: The Single Pass Approach

The idea behind this approach is to walk through the inputted array and check the value at each index. If the value at the index is the target value, then return that index. If the value is larger than the target value, then we know the target would have been at the index that we're currently on, and the rest of the array would be shifted over, so we also can return that index. Finally, if we're at the end of the array, and we still haven't met or exceeded the value of the target, then we know the target would be appended to the end of the array, so we can return the length of the array as the index.

To break done what I mean with an example, if the inputted array was [1, 3, 5], and the target was 3, we'd check each element of the array. At index 1, 3 = 3, so we'd return 1.

If the inputted array was [1, 3, 5], and the target was 4, we'd again check each element of the array. We never find the element 4, but at index 2, 5 is greater than 4, so we know that if 4 was in the array, it would be found at index 2. Therefore, we'd return the index 2.

In a third example, if the inputted array was still [1, 3, 5], but the target was 6, we'd still check each element of the array. However, we'd get to the end of the array, and still not find a number equal to or larger than the target, which means if 6 were in the array, it would come at the very end. Therefore, we'd return index 3.

Coding the First Method

In this first approach, we'll want to walk through the array using a for loop.

function searchInsert1(nums, target) {
  for (let i = 0; i < nums.length; i++) {
    //...
  }
}

At each element in the nums array, we want to check for two things: is the element equal to the target, or is the element larger than the target? In both cases, we know that the index we're on is the index we want to return, so we can simply return i.

function searchInsert1(nums, target) {
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] === target || nums[i] > target) {
      return i;
    }
    //...
  }
}

If we get to the end of the nums array and still haven't found an element equal to or larger than the target, then we know our target would come at the end of the array, so we can return the length of the nums array, which would the index of one more element tacked on to the end of the array.

function searchInsert1(nums, target) {
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] === target || nums[i] > target) {
      return i;
    }
    if (i === nums.length - 1) {
      return nums.length;
    }
  }
}

Method #2: The Binary Search Approach

In this approach, we'd want to do a binary search on the sorted array. We'd create two end points, starting at each end of the array, and would find the middle point between them. If the middle point equals the target, we can return that point. If the middle point is greater than the target, then we know we should move the search frame over, and make the end equal to the middle point. If the middle point is less than the target, we know we should move the search frame over, this time making the start equal to the middle point.

We'd use a while loop to keep doing this until the start point was larger than the end point. If that happened, and we never returned the middle point, then we know the target is not in the array, so we can return the start point.

I think binary searches are harder to explain in words without having code right next to it, so I'll try to clear up this approach while working through the solution.

Coding the Second Method

In order to start a binary search, we'd have to have two indexes: the start point, index 0, and the end point, nums.length-1.

function searchInsert2(nums, target) {
  let start = 0;
  let end = nums.length - 1;

  //...
}

We want to build a while loop to continually checking the middle point. We'll keep checking until the start index is greater than the end index.

Inside the while loop, we'll make a variable called midPoint, which we can find by adding the start and end index, dividing by 2, and doing Math.floor() on that result.

function searchInsert2(nums, target) {
  let start = 0;
  let end = nums.length - 1;

  while (start <= end) {
    const midPoint = Math.floor((start + end) / 2);
    //...
  }
  //...
}

If the middle point is the target, we've found our answer, so we can return midPoint, which is the index of the target.

If the middle point is larger than the target, we know we should be changing the end points of the search, moving it more toward the start of the array. Therefore, we should change end to be midPoint - 1, and also tell the function to continue on to the next round in the while loop.

function searchInsert2(nums, target) {
  let start = 0;
  let end = nums.length - 1;

  while (start <= end) {
    const midPoint = Math.floor((start + end) / 2);
    if (nums[midPoint] === target) return midPoint;
    if (nums[midPoint] > target) {
      end = midPoint - 1;
      continue;
    }
    //...
  }
  //...
}

If the middle point is less than the target, we know our end points are off, and should instead be searching in the latter half of the array. Therefore, we should set start equal to midPoint + 1, and continue on in the while loop.

function searchInsert2(nums, target) {
  let start = 0;
  let end = nums.length - 1;

  while (start <= end) {
    const midPoint = Math.floor((start + end) / 2);
    if (nums[midPoint] === target) return midPoint;
    if (nums[midPoint] > target) {
      end = midPoint - 1;
      continue;
    }
    if (nums[midPoint] < target) {
      start = midPoint + 1;
      continue;
    }
  }
  //...
}

The last thing to do will be to add a return statement outside of the while loop. If, after checking all of the elements in the nums array, we never found the target value, and we've reached the point that start is now larger than end, we know the index value of the target would be at start, so we can return start.

function searchInsert2(nums, target) {
  let start = 0;
  let end = nums.length - 1;

  while (start <= end) {
    const midPoint = Math.floor((start + end) / 2);
    if (nums[midPoint] === target) return midPoint;
    if (nums[midPoint] > target) {
      end = midPoint - 1;
      continue;
    }
    if (nums[midPoint] < target) {
      start = midPoint + 1;
      continue;
    }
  }
  return start;
}