c语言实现二分查找的算法

在计算机科学中，二分查找是一种搜索算法，其输入为一个有序数组和一个要查找的元素。该算法首先将中间元素与要查找的元素进行比较，如果中间元素大于要查找的元素，则在数组的左半部分继续进行查找，否则在数组的右半部分继续进行查找，直到找到元素为止。二分查找的时间复杂度为O(log n)，是一种非常高效的查找算法。本文将讨论如何用C语言实现二分查找的算法。

1. 二分查找的基本思想

二分查找的基本思想是将一个有序序列进行二分，每次取中间值进行比较，如果等于要查找的值，则返回该位置，否则继续将序列二分查找，直到找到为止。

例如，对于有序序列[2, 4, 6, 8, 10, 12, 14, 16, 18, 20]，我们要查找元素12的位置。首先取序列的中间值10，由于10小于12，因此需要在序列的右半部分继续查找。接下来，取右半部分的中间值14，由于14大于12，因此需要在序列的左半部分继续查找。继续取左半部分的中间值6，由于6小于12，因此需要在序列的右半部分继续查找。接下来，取右半部分的中间值12，由于12等于要查找的元素，因此返回该位置4。

2. 二分查找的C语言实现

下面是在C语言中实现二分查找的代码：

```c

int binary_search(int array[], int n, int target) {

int left = 0, right = n - 1;

while (left <= right) {

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

if (array[mid] == target)

return mid;

else if (array[mid] < target)

left = mid + 1;

else

right = mid - 1;

}

return -1;

}

```

该函数接受三个参数：一个整型数组array，数组的长度n，要查找的目标值target。函数返回要查找的目标值在数组中的下标，如果目标值不存在，则返回-1。

3. 二分查找的变体

除了基本的二分查找算法，还有一些变体的算法。

3.1 查找第一个等于目标值的元素

如果需要查找第一个等于目标值的元素，可以稍微修改二分查找算法。具体做法是：当中间值等于要查找的值时，不直接返回，而是向左边继续查找，直到找到第一个等于要查找的值的元素。

修改后的代码如下所示：

```c

int binary_search_first(int array[], int n, int target) {

int left = 0, right = n - 1;

while (left <= right) {

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

if (array[mid] >= target)

right = mid - 1;

else

left = mid + 1;

}

if (left < n && array[left] == target)

return left;

else

return -1;

}

```

3.2 查找最后一个等于目标值的元素

如果需要查找最后一个等于目标值的元素，可以稍微修改二分查找算法。具体做法是：当中间值等于要查找的值时，不直接返回，而是向右边继续查找，直到找到最后一个等于要查找的值的元素。

修改后的代码如下所示：

```c

int binary_search_last(int array[], int n, int target) {

int left = 0, right = n - 1;

while (left <= right) {

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

if (array[mid] > target)

right = mid - 1;

else

left = mid + 1;

}

if (right >= 0 && array[right] == target)

return right;

else

return -1;

}

```

3.3 查找第一个大于等于目标值的元素

如果需要查找第一个大于等于目标值的元素，可以稍微修改二分查找算法。具体做法是：当中间值小于目标值时，向右继续查找；当中间值大于等于目标值时，向左继续查找，直到找到第一个大于等于目标值的元素。

修改后的代码如下所示：

```c

int binary_search_greater(int array[], int n, int target) {

int left = 0, right = n - 1;

while (left <= right) {

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

if (array[mid] < target)

left = mid + 1;

else

right = mid - 1;

}

if (left < n)

return left;

else

return -1;

}

```

4. 总结

本文分析了二分查找的基本思想和C语言实现，以及三种常见的变体算法。通过这篇文章，读者可以学习到如何用C语言实现二分查找的算法，并且了解到如何处理一些变体问题，为以后的编程工作打下坚实的基础。