Viiisit [LeetCode] - 35. Search Insert Position

keep learning, keep coding!

Problem - 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.

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

翻譯蒟蒻

在一個已經排序且元素各不相同的整數陣列中，找到目標值的索引。如果目標值存在於陣列中，則返回其索引；如果目標值不在陣列中，則返回他應該插入的位置的索引，使得插入後仍保持陣列的排序狀態，且要求必須達到 O(log n) 的時間複雜度。

---

• Example 1:

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

• Example 2:

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

• Example 3:

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

---

若使用二分搜尋（Binary Search），嘗試在陣列中找到中間元素，將目標值與中間元素進行比較。如果目標值等於中間元素，則返回中間元素的索引；如果目標值小於中間元素，則在左半部分繼續搜尋；如果目標值大於中間元素，則在右半部分繼續搜尋。（於 Solution 1 中實作）

---

Solution - JavaScript

Solution 1:

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

  while (low <= high) {
    let mid = Math.floor(low + (high - low) / 2);
    if (nums[mid] === target) {
      return mid;
    } else if (nums[mid] < target) {
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }
  return low;
};

Solution 2:

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var searchInsert = function(nums, target) {
  for(let i = 0; i < nums.length; i++) {
    if (nums[i] >= target) {
      return i;
    }
  }
  return nums.length;
};

Solution - Ruby

Solution 1:

def search_insert(nums, target)
  low = 0
  high = nums.size - 1
  while low <= high
    mid = (low + high) / 2
    if nums[mid] == target
      return mid
    elsif nums[mid] < target
      low = mid + 1
    else
      high = mid - 1
    end
  end
  low
end

Solution 2:

def search_insert(nums, target)
  for i in 0...nums.size
    return i if nums[i] >= target
  end
  return nums.size
end

Solution - PHP

Solution 1:

function searchInsert($nums, $target) {
  $low = 0;
  $high = count($nums) - 1;
  while ($low <= $high) {
    $mid = $low + floor(($high - $low) / 2);
    if ($nums[$mid] == $target) {
      return $mid;
    } else if ($nums[$mid] < $target) {
      $low = $mid + 1;
    } else {
      $high = $mid - 1;
    }
  }
  return $low;
}

Solution 2:

function searchInsert($nums, $target) {
  for ($i = 0; $i < count($nums); $i++) {
      if ($nums[$i] >= $target) {
      return $i;
      }
  }
  return count($nums);
}

LeetCode 傳送門 - Search Insert Position