企业官网建设流程全解析

一、什么是二分算法

二分算法（Binary Search）是一种在有序数据集合中快速查找目标元素的算法。它的核心思想非常朴素：每次把搜索范围缩小一半，通过比较中间元素与目标值的大小关系，决定下一步只在左半区间还是右半区间继续查找。

正因为每次都能排除掉一半的候选数据，二分算法的时间复杂度为O(log n)，在数据量较大时相比线性查找的O(n)有非常明显的优势。例如在 10 亿个有序数据中查找一个元素，线性查找最坏需要比较 10 亿次，而二分查找最多只需要约 30 次。

使用二分算法的前提是数据必须有序（或具备单调性）。如果数据无序，需要先排序，排序本身通常需要O(n log n)的时间。

二、二分算法的基本思想

二分查找的过程可以用三个指针来描述：

• left：当前搜索区间的左边界。
• right：当前搜索区间的右边界。
• mid：当前搜索区间的中间位置，通常取mid = left + (right - left) / 2。

每一轮循环中，比较nums[mid]与目标值target：

1. 如果nums[mid] == target，说明找到了目标，直接返回下标。
2. 如果nums[mid] < target，说明目标只可能在右半区间，令left = mid + 1。
3. 如果nums[mid] > target，说明目标只可能在左半区间，令right = mid - 1。

当left > right时，搜索区间为空，说明目标不存在。

三、二分查找的执行流程

下面用流程图展示标准二分查找的完整执行过程：

flowchart TD A[开始: left=0, right=n-1] --> B{left <= right ?} B -- 否 --> C[返回 -1, 未找到] B -- 是 --> D[计算 mid = left + right-left/2] D --> E{nums[mid] == target ?} E -- 是 --> F[返回 mid] E -- 否 --> G{nums[mid] < target ?} G -- 是 --> H[left = mid + 1] G -- 否 --> I[right = mid - 1] H --> B I --> B

四、代码实现

4.1 C 语言实现

下面是标准二分查找的 C 语言实现，返回目标元素的下标，不存在时返回-1：

#include <stdio.h> int binarySearch(int nums[], int n, int target) { int left = 0; int right = n - 1; while (left <= right) { /* 防止 (left + right) 溢出 */ int mid = left + (right - left) / 2; if (nums[mid] == target) { return mid; } else if (nums[mid] < target) { left = mid + 1; } else { right = mid - 1; } } return -1; } int main(void) { int nums[] = {1, 3, 5, 7, 9, 11, 13}; int n = sizeof(nums) / sizeof(nums[0]); printf("%d\n", binarySearch(nums, n, 7)); /* 输出 3 */ printf("%d\n", binarySearch(nums, n, 8)); /* 输出 -1 */ return 0; }

4.2 代码说明

• 数组长度：C 语言中数组不会自带长度，需要额外传入n，通常用sizeof(nums) / sizeof(nums[0])计算。
• 下标类型：这里用int表示下标，若数组长度可能超过INT_MAX，应改用long long或size_t。
• 溢出处理：mid = left + (right - left) / 2可以避免left + right溢出。
• 返回值：找到时返回下标，未找到时返回-1，调用方需要自行判断返回值是否有效。

五、边界问题与常见坑

5.1 区间定义要统一

二分最容易出错的地方是边界处理。写代码前必须先明确自己使用的是哪种区间定义：

两种写法都能正确工作，但不能混用。混用会导致死循环或漏查元素。

5.2 中间值溢出

当left和right都很大时，left + right可能超出整型范围。推荐写成mid = left + (right - left) / 2，避免溢出。

5.3 死循环

如果更新边界时写成left = mid而不是left = mid + 1，在left与right相邻时mid会一直等于left，从而陷入死循环。记住：已经判断过的 mid 位置必须被排除出下一轮区间。

六、二分算法的常见变体

实际题目中，二分往往不是简单地“找一个数”，而是寻找满足某个条件的边界：

• 查找第一个等于 target 的位置：找到相等元素后不立即返回，而是继续收缩右边界。
• 查找最后一个等于 target 的位置：找到相等元素后继续收缩左边界。
• 查找第一个大于等于 target 的位置（lower_bound）：常用于插入位置、区间统计等问题。
• 查找最后一个小于等于 target 的位置（upper_bound 的变体）。

这些变体的共同点是：把“是否找到”转化为“是否满足某个单调条件”，从而把二分从查找问题推广到答案判定问题。