Practice: Find Zero Position

In this assignment, we will explore how to use binary search to solve a specific problem: Finding Zero Position.

Problem Description

// Write a function named `findZeroPosition` that takes in a
// sorted array of distinct integers as input.
// The function should return the index where the value 0 is
// found in the array, or the index where it would be inserted if
// it were not found.

// If the value 0 is found in the array, the function should
// return the index of the value 0. If the value 0 is not found,
// the function should return the index where it would be inserted
// while maintaining the sorted order of the array.

// Example:
// Input: nums = [-7, -5, -3, 0, 2]
// Output: 3

// Example:
// Input: nums = [3, 5, 7, 9, 11]
// Output: 0

Walkthrough

Let's now walk through the step-by-step solution for the first test case [-7, -5, -3, 0, 2]. We will first write the template from the previous assignment for easier reference.

let left = 0
let right = array.length - 1
while (left <= right) {
  let mid = Math.floor((left + right) / 2)
  if (array[mid] === target) {
    // Optional early return
  } else if (***comparison***) {
    left = mid + 1
  } else {
    right = mid - 1
  }
}

Step 1: We initialize the left pointer at index 0 and the right pointer at index nums.length - 1, or number 4 in this case. These pointers represent the starting and ending indices of the search range.

Step 2: In the second step, we enter the binary search loop. First, we calculate the mid index, which is (0 + 4) / 2, giving us 2. The number at index 2 is -3. Since it is less than zero, we reassign left to mid + 1, which is 3, thus eliminating the left half of the array.

Step 3: In the third and final step, we calculate mid once again, (3 + 4) / 2, which gives us 3 (rounded down). The number at index 3 is 0, which is our target number, so our search stops.

---

Now let's apply this step-by-step approach to the given test case where the array is [3, 5, 7, 9, 11]:

Step 1: We initialize the left pointer at index 0 and the right pointer at index nums.length - 1, or number 4 in this case. These pointers represent the starting and ending indices of the search range.

Step 2: In the second step, we enter the binary search loop. First, we calculate the mid index, which is (0 + 4) / 2, giving us 2. The number at index 2 is 7. Since it is greater than zero, we reassign right to mid - 1, which is 1, thus eliminating the right half of the array.

Step 3: In the third step, we calculate mid, (0 + 1) / 2, which, rounded down gives us 0. The number at index 0 is 3, which is still greater than zero. We reassign right pointer to mid - 1 which is -1 thus exiting the loop. In the end, we return the value that left variable holds.

---

You might wonder if returning the value held by the left variable would work in every situation. What if the value that needs to be inserted is at the end of the array? Trust us, this approach will work in every scenario. Let's further illustrate this with an example using the array [-8, -7, -5, -2, -1].

Step 1: We begin by initializing the left pointer at index 0 and the right pointer at index 4, representing the starting and ending indices of the search range.

Step 2: In the next step, we enter the binary search loop. We calculate the mid index using the formula (0 + 4) / 2, which gives us 2. The element at index 2 is -5, which is smaller than zero. Consequently, we reassign the left pointer to mid + 1, resulting in 3 and effectively eliminating the left half of the search range.

Step 3: Moving forward, we proceed to the next iteration. We calculate the new mid index using the formula (3 + 4) / 2, which yields 3 when we round it down. The element at index 3 is -2, still smaller than zero. As a result, we reassign the left pointer to mid + 1, leading to 4.

Step 4: In the next step, we calculate the new mid index using the formula (4 + 4) / 2, which yields 4. We see that the element at index 4 is -1 still less than zero. We reassign left to mid + 1. left is greater than right now, so we exit the loop and return the value that variable left holds which is index 5.

Solution Code

Here is the coded solution in JavaScript, using our template from the previous lesson:

function findZeroPosition(nums) {
  let left = 0;
  let right = nums.length - 1;
  while (left <= right) {
    let mid = Math.floor((left + right) / 2);
    if (nums[mid] === 0) {
      return mid;
    } else if (nums[mid] < 0) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  return left;
}

console.log(findZeroPosition([-7, -5, -3, 0, 2])); // 3
console.log(findZeroPosition([3, 5, 7, 9, 11])); // 0
console.log(findZeroPosition([-8, -7, -5, -2, -1])); // 5

Time Complexity

The time complexity of the binary search algorithm is O(logN), which allows us to perform the search in a significantly faster time compared to linear search, especially for large arrays.

Keep in mind that this solution relies on the array being sorted. If the array is not sorted, we would need to sort it first or use a different approach.

Now that we understand the problem and have explored the step-by-step solution, we are ready to apply our knowledge to solve another problem using binary search.