数组操作：二分查找与元素移除

数组操作：二分查找与元素移除

本篇介绍两种常见的数组操作算法：二分查找和元素移除。

二分查找

给定一个有序数组和目标值，使用二分查找确定目标值在数组中的索引，若不存在则返回-1。

算法流程：

1. 初始化左指针 left 指向数组首元素，右指针 right 指向数组尾元素。
2. 当 left <= right 时，循环执行以下操作：
   • 计算中间索引 mid = (left + right) // 2。
   • 若 nums[mid] 等于目标值，返回 mid。
   • 若 nums[mid] 小于目标值，令 left = mid + 1，继续在右侧子数组中查找。
   • 若 nums[mid] 大于目标值，令 right = mid - 1，继续在左侧子数组中查找。
3. 若循环结束仍未找到目标值，返回 -1。

代码示例(Python):

def binary_search(nums, target):
  """
  二分查找
  """
  left, right = 0, len(nums) - 1
  while left <= right:
    mid = (left + right) // 2
    if nums[mid] == target:
      return mid
    elif nums[mid] < target:
      left = mid + 1
    else:
      right = mid - 1
  return -1

元素移除

给定一个数组和目标值，原地移除数组中所有等于目标值的元素，并返回移除后数组的新长度。

算法流程：

1. 初始化慢指针 slow 和快指针 fast，均指向数组首元素。
2. 遍历数组，当 fast 指针指向的元素不等于目标值时，将该元素复制到 slow 指针位置，并将 slow 指针移动一位。
3. 循环结束后，slow 指针指向的位置即为新数组的尾元素，返回 slow。

代码示例(Python):

def remove_element(nums, val):
  """
  移除数组中指定元素
  """
  slow = 0
  for fast in range(len(nums)):
    if nums[fast] != val:
      nums[slow] = nums[fast]
      slow += 1
  return slow