二分搜索（Binary Search）

二分搜索是一种在有序数组中查找特定元素的算法。假设我们要搜索x，搜索过程从数组的中间元素开始，如果中间元素正好是x，而查找成功；否则我们利用中间位置将数组分为前、后两个子数组。如果x小于中间位置的元素，则进一步查找前一个子数组，否则进一步查找后一个子数组。重复以上步骤，直到找到满足条件的元素，或直到子数组不存在为止，代表查找不成功。

思路：

  • 从数组中的中间元素开始，如果中间元素刚好是X，则查找成功
  • 否则我们利用中间位置将数组分为前、后两个子数组
    • 如果X小于中间元素，则进一步查找前一个子数组
    • 否则进一步查找后一个子数组
  • 重复以上步骤，直到找到满足条件的元素，或直到子数组不存在为止，代表查找不成功