二分查找算法

二分查找：通过不断将数组分成两半，逐步缩小搜索范围，从而快速找到目标元素。以下是二分查找算法的步骤：

  1. 初始条件：数组必须是有序的。
  2. 定义搜索范围：初始时搜索范围是数组的整个范围，定义两个指针，left 和 right，分别指向数组的起始和末尾位置。
  3. 计算中间点：计算中间位置 mid，mid = left + (right - left) / 2。
  4. 比较中间点元素：
    如果中间点的元素等于目标元素，则查找成功，返回该元素的索引。
    如果中间点的元素大于目标元素，则目标元素只可能在左半部分，将 right 更新为 mid - 1。
    • 如果中间点的元素小于目标元素，则目标元素只可能在右半部分，将 left 更新为 mid + 1。
  5. 重复步骤 3 和 4，直到找到目标元素或搜索范围为空（left > right）。
#include <stdio.h>


int binarySearch(int arr[], int size, int target) {
    int left = 0;
    int right = size - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (arr[mid] == target) {
            return mid; // 找到目标元素，返回其索引
        } else if (arr[mid] > target) {
            right = mid - 1; // 目标元素在左半部分
        } else {
            left = mid + 1; // 目标元素在右半部分
        }
    }
    
    return -1; // 未找到目标元素
}

int main() {
    int list[] = {3, 6, 8, 12, 14, 17, 25, 29, 31, 36, 42, 47, 53, 55, 62};
    int size = sizeof(list) / sizeof(list[0]); //整个数组的字节数除以单个元素的字节数，计算数组元素个数
    int target = 25;
    
    int result = binarySearch(list, size, target);
    
    if (result != -1) {
        printf("元素 %d 在数组中的索引是 %d\n", target, result);
    } else {
        printf("未找到元素 %d\n", target);
    }
    
    return 0;
}