C语言小试身手：实现二分搜索算法

本文主要是介绍C语言小试身手：实现二分搜索算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

开篇

本篇文章的主题是使用C语言实现简单的二分搜索算法，题目来源于《编程珠玑》第4章。

问题概要

用C语言实现简单的二分搜索算法，确定排序后的数组x[0…n-1]中是否存在目标元素t。

思路分析

这个问题的思路比较简单，因为是排序后的数组，所以不断用中值去和目标元素t去比较，然后根据大小来调整。举个例子：
假如有数组x=[1, 3, 7, 9, 12],需要查找目标元素t=5在不在数组内
首先，l = 0, u = 4, m = (0+4)/2 = 2, 注意，这里l,u,m都是对应的数组x的索引;
x[2]=7, 7>5, 所以调整u = (2-1) = 1, 此时m=(1+1) / 2= 1
x[1]= 3, 3<5, 所以调整l = (1+1)=2 , l > u, 跳出循环，返回-1,代表没有找到。

代码实现

#include <stdio.h>int binary_search(int x[], int n, int t) {int l = 0;int u = n - 1;int p = -1;// 初始化为-1，代表不存在while (l <= u) {int m = (l + u) / 2;if (x[m] < t) {l = m + 1;}else if(x[m] == t) {p = m;break;}else {u = m - 1;}}return p;
}int main() {int x[] = { 3, 7, 8, 19, 16 };int n = sizeof(x) / sizeof(x[0]);int t = 19;int result = binary_search(x, n, t);if (result != -1) {printf("%d在数组的index为%d\n", t, result);}else {printf("%d不存在于数组中.\n", t);}return 0;
}