二分查找与双指针算法应用实例

介绍两种常用算法在数组操作中的应用：

1. 力扣 704. 二分查找

二分查找算法适用于在一个有序数组中查找特定元素。其核心思想是不断将搜索区间减半，直到找到目标元素或搜索区间为空。

算法步骤:

  • 初始化两个指针 left 和 right，分别指向数组的起始和结束位置。
  • 当 left <= right 时，执行循环：
    • 计算中间位置 mid = (left + right) // 2。
    • 如果 nums[mid] 等于目标值，则返回 mid。
    • 如果 nums[mid] 小于目标值，则将 left 更新为 mid + 1。
    • 如果 nums[mid] 大于目标值，则将 right 更新为 mid - 1。
  • 如果循环结束仍未找到目标值，则返回 -1。

2. 力扣 27. 移除元素

移除元素问题要求从数组中移除所有等于特定值的元素，并返回最终数组的新长度。双指针方法可以高效地解决这个问题。

算法步骤:

  • 初始化两个指针 slow 和 fast，均指向数组的起始位置。
  • 遍历数组，当 nums[fast] 不等于目标值时，将 nums[fast] 的值赋给 nums[slow]，并将 slow 指针向后移动一位。
  • 遍历结束后，slow 指针指向的位置即为新数组的长度。

二分查找和双指针算法是解决数组相关问题的常用技巧。 理解其工作原理并熟练运用，可以提高代码效率和解决问题的灵活性。