折半查找 | 邃境

折半查找或者叫做二分查找

折半查找的前提条件是：

待查找的数组或列表必须是有序的，按照升序或降序排列。

折半查找的步骤如下：

初始化左右边界：将左边界设为数组的起始位置，将右边界设为数组的末尾位置。
计算中间位置：通过取左右边界的平均值，得到中间位置。即，mid = (left + right) / 2。
比较中间元素与目标值：
- 如果中间元素等于目标值，则找到了目标元素，返回中间位置。
- 如果中间元素大于目标值，则目标元素可能在左半部分，更新右边界为中间位置减一，即 right = mid - 1。
- 如果中间元素小于目标值，则目标元素可能在右半部分，更新左边界为中间位置加一，即 left = mid + 1。
重复步骤2和步骤3，直到找到目标元素或左边界大于右边界。如果左边界大于右边界，则表示目标元素不存在于数组中。

折半查找的时间复杂度为 O(log n) ，其中n是数组或列表的长度。这是因为每次比较都将查找范围折半，每次排除一半的元素，因此查找的时间复杂度是对数级别的。折半查找在大型有序数据集上是非常高效的。

递归方法一般方法

#include <stdio.h>

int binarySearchRecursive(int arr[], int left, int right, int target) {
  if (left <= right) {
    int mid = left + (right - left) / 2;

    if (arr[mid] == target) {
      return mid;
    }

    if (arr[mid] < target) {
      return binarySearchRecursive(arr, mid + 1, right, target);
    }

    return binarySearchRecursive(arr, left, mid - 1, target);
  }

  return -1;
}

int main() {
  int arr[] = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20};
  int n = sizeof(arr) / sizeof(arr[0]);
  int target = 12;
  int result = binarySearchRecursive(arr, 0, n - 1, target);

  if (result == -1) {
    printf("Element not found\n");
  } else {
    printf("Element found at index %d\n", result);
  }

  return 0;
}

#include <stdio.h>

int binarySearchIterative(int arr[], int n, int target) {
  int left = 0;
  int right = n - 1;

  while (left <= right) {
    int mid = left + (right - left) / 2;

    if (arr[mid] == target) {
      return mid;
    }

    if (arr[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  return -1;
}

int main() {
  int arr[] = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20};
  int n = sizeof(arr) / sizeof(arr[0]);
  int target = 12;
  int result = binarySearchIterative(arr, n, target);

  if (result == -1) {
    printf("Element not found\n");
  } else {
    printf("Element found at index %d\n", result);
  }

  return 0;
}