二分查找算法

算法思路

二分查找算法是一种用于在有序数组中查找特定元素的算法。它的基本思想是将目标元素与数组的中间元素进行比较，然后根据比较结果缩小查找范围，直到找到目标元素或确定目标元素不存在。

算法的步骤如下：

1. 初始化左边界 left 为数组的第一个元素的索引，右边界 right 为数组的最后一个元素的索引。
2. 在每一次迭代中，计算中间元素的索引 mid，可以使用 mid = left + (right - left) / 2 来避免整数溢出。
3. 将目标元素与中间元素进行比较。
   • 如果目标元素等于中间元素，说明找到了目标元素，返回中间元素的索引。
   • 如果目标元素小于中间元素，说明目标元素可能在左半部分，更新右边界 right 为 mid - 1。
   • 如果目标元素大于中间元素，说明目标元素可能在右半部分，更新左边界 left 为 mid + 1。
4. 重复步骤 2 和步骤 3，直到左边界大于右边界。
5. 如果左边界大于右边界，说明目标元素不存在于数组中，返回 $-1$。

二分查找算法的关键在于通过每一次比较，将查找范围缩小一半，从而快速地逼近目标元素。由于每次迭代都将查找范围减半，所以算法的时间复杂度为 $O(log n)$，其中 $n$ 是数组的大小。

需要注意的是，二分查找算法要求数组是有序的。如果数组未排序，需要先对数组进行排序，然后再进行二分查找。

编程实现

int binarySearch(int *nums, int numsSize, int target)
{
  int left = 0, right = numsSize - 1;
  while (left <= right)
  {
    int mid = left + (right - left) / 2;
    if (nums[mid] == target)
      return mid;
    if (nums[mid] < target)
      left = mid + 1;
    else
      right = mid - 1;
  }
  return -1;
}