C语言-二分查找

 二分查找

二分查找（Binary Search）是一种在有序数组中查找特定元素的搜索算法。它的工作原理是将数组分为两半，然后根据目标值与中间元素的关系，决定在左半部分还是右半部分继续搜索，直到找到目标值或者搜索范围为空。
二分查找算法的基本步骤如下：
1. 确定查找范围，初始时为整个数组。
2. 在查找范围内找到中间元素。
3. 比较中间元素与目标值：
   - 如果中间元素等于目标值，则查找成功，返回中间元素的索引。
   - 如果目标值小于中间元素，则在左半部分继续查找。
   - 如果目标值大于中间元素，则在右半部分继续查找。
4. 重复步骤2和3，直到找到目标值或者查找范围为空。
二分查找的时间复杂度为 \( O(\log n) \)，其中 \( n \) 是数组的长度。这是因为每次迭代可以将查找范围减少一半。
下面是一个简单的二分查找

#include <stdio.h>

// 函数声明
int binarySearch(int arr[], int size, int target);

int main() {
    int arr[] = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
    int target = 7;
    int size = sizeof(arr) / sizeof(arr[0]);
    int index = binarySearch(arr, size, target);

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

    return 0;
}

// 函数定义
int binarySearch(int arr[], int size, int target) {
    int low = 0;
    int high = size - 1;
    int mid;

    while (low <= high) {
        mid = (low + high) / 2;  // C 语言中的整数除法
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }

    return -1;  // 目标值不在数组中
}

在这个例子中，我们定义了一个 binarySearch 函数，它接受一个整数数组 arr、数组的大小 size 和要查找的目标值 target。函数返回目标值在数组中的索引，如果目标值不在数组中，则返回 -1。在 main 函数中，我们创建了一个有序数组 arr，并调用 binarySearch 函数来查找目标值 target。如果找到目标值，它将打印出目标值的索引；如果没有找到，它将打印出目标值不在数组中的消息。

代码的解释

这段代码是一个简单的 C 语言程序，它使用二分查找算法在给定的数组中查找一个特定的目标值。以下是代码的逐行解释：
 

#include <stdio.h>

这行代码是预处理器指令，它告诉编译器包含标准输入输出头文件 `stdio.h`，这个文件包含了标准输入输出函数，如 `printf` 和 `scanf`。

// 函数声明
int binarySearch(int arr[], int size, int target);

这行代码是函数声明，它声明了一个名为 `binarySearch` 的函数，该函数接受三个整数参数：一个整数数组 `arr`、数组的大小 `size` 和目标值 `target`。函数返回一个整数，表示目标值在数组中的索引，如果目标值不在数组中，则返回 -1。

int main() {
    int arr[] = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
    int target = 7;
    int size = sizeof(arr) / sizeof(arr[0]);
    int index = binarySearch(arr, size, target);

`main` 函数是程序的入口点。它首先定义了一个整数数组 `arr` 和一个整数 `target`，然后计算数组的大小 `size`，最后调用 `binarySearch` 函数来查找目标值，并将返回的索引存储在变量 `index` 中。

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

这部分代码使用条件语句来检查 `binarySearch` 函数是否找到了目标值。如果找到了，它将打印出目标值在数组中的索引；如果没有找到，它将打印出目标值不在数组中的消息。

    return 0;
}

`main` 函数的返回值是 0，这表示程序正常结束。

// 函数定义
int binarySearch(int arr[], int size, int target) {
    int low = 0;
    int high = size - 1;
    int mid;

这部分代码是 `binarySearch` 函数的定义。它首先定义了三个整数变量：`low`、`high` 和 `mid`。`low` 初始化为数组的第一个元素的索引（即 0），`high` 初始化为数组的最后一个元素的索引（即 `size - 1`）。`mid` 用于存储中间元素的索引。

    while (low <= high) {
        mid = (low + high) / 2;  // C 语言中的整数除法
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }

这部分代码是一个循环，它重复执行以下步骤，直到 `low` 大于 `high`：
1. 计算中间元素的索引 `mid`。
2. 检查中间元素是否等于目标值。如果是，则返回中间元素的索引。
3. 如果中间元素小于目标值，则将 `low` 设置为 `mid + 1`，并继续搜索数组的右半部分。
4. 如果中间元素大于目标值，则将 `high` 设置为 `mid - 1`，并继续搜索数组的左半部分。

    return -1;  // 目标值不在数组中
}

如果循环完成而没有找到目标值，函数返回 -1，表示目标值不在数组中。
总结来说，这段代码定义了一个二分查找函数，并在 `main` 函数中使用该函数在一个已排序的整数数组中查找一个特定的目标值，并打印出结果。
 

图解

一次干掉一半

前提是有序

折半查找

找一次，去掉一半

在有序的数字里，查找某一个数字

找到了

数值在左边

数值在右边

方法一（循环查找） 

方法2（二分查找）

二分查找

但是前提必粗是有序

代码实现

只要left

求平均值

这个方式会更好

代码总结 

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>


int main()
{
	int arr[] = { 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30 };
	
	int j = 0;
	scanf("%d", &j);

	

	int sz = sizeof(arr) / sizeof(arr[0]);//数组的总数，从1开始算

	int left = 0;//左下标
	int right = sz - 1;//减去1 才等于下标 这里是下标的意思

	//int mid = (left + right) / 2;
	//不能给外面是因为此时没有进入循环 mid的数值是确定的 不会随着循环发生改变

	while (left <= right)
	{
		int mid = (left + right) / 2;
		if (arr[mid] < j)//这里也就是如果中间值大的话 那实际输入的就小，可以再次循环排查
		{
			left = mid + 1;//是因为中间值的不算进去的，然后既然已经 在else里面做排除所以加上会节约算法时间
		}
		else if (arr[mid] > j)
		{
			right = mid - 1;
		}
		else if (arr[mid] == j)
		{
			printf("找到了，下标是：%d\n", mid);
			break;
			
		}
		else
		{
			printf("傻子仔细看看，没有这个数组");
			break;
		}
		//printf("傻子仔细看看，没有这个数组");
		//break;
	}

	/*printf("傻子仔细看看，没有这个数组");*/


	return 0;
}