目录引言代码详解拓展内容有序字典的奇妙之处避免使用全局变量引言大家好今天我们将进入一个充满神奇魔力的世界——二分查找。在这个世界里我们将用有序的字典来展开一场刺激的探险寻找我们心仪的元素。快跟我一起来开启二分查找的奇妙之旅吧代码详解#include stdio.h #define LEN 10 // global variable: file scope // avoid using global variables as possible as you can /** * Search for the key in the dict. * param key The key to search for. * param dict The dictionary to search. * param len The length of the dict. * return the index of the key in the dict if found, -1 otherwise */ int BinarySearch(int key, const int dict[], int len); int main() { int dictionary[LEN] {1, 1, 2, 3, 5, 8, 13, 21, 34, 55}; int key 0; scanf(%d, key); int index BinarySearch(key, dictionary, LEN); if (index -1) { printf(Not found!\n); } else { printf(The index of %d is %d.\n, key, index); } return 0; } int BinarySearch(int key, const int dict[], int len) { int low 0; int high len - 1; while (low high) { int mid (low high) / 2; if (key dict[mid]) { low mid 1; } else if (key dict[mid]) { high mid - 1; } else { return mid; } } return -1; }让我们一行行地来解读这段代码吧首先在代码开头我们定义了一个宏LEN它表示字典的长度。这个宏的作用就像是在迷宫中告诉我们迷宫的尺寸让我们可以更好地探索其中的秘密。然后我们定义了一个函数BinarySearch它用于在字典中搜索特定的关键字。这个函数采用了三个参数key是要搜索的关键字dict是待搜索的有序字典len是字典的长度。函数的返回值是关键字在字典中的索引如果没有找到则返回 -1。int BinarySearch(int key, const int dict[], int len) { int low 0; int high len - 1; while (low high) { int mid (low high) / 2; if (key dict[mid]) { low mid 1; } else if (key dict[mid]) { high mid - 1; } else { return mid; } } return -1; }在我们的搜索函数中我们使用了两个变量low和high来分别标记搜索范围的最低位置和最高位置。这就像是迷宫探险中的两扇门我们通过不断调整它们的位置逐步缩小搜索范围直到找到我们想要的宝藏。我们使用了一个while循环来迭代搜索。在循环中我们通过计算中间位置mid来确定当前搜索范围的中间元素。然后我们将关键字与中间元素进行比较如果大于中间元素则将low更新为mid 1将搜索范围缩小到右半部分如果小于中间元素则将high更新为mid - 1将搜索范围缩小到左半部分。如果关键字等于中间元素说明我们找到了宝藏直接返回中间元素的索引。如果经过循环后仍然没有找到宝藏说明字典中没有该关键字我们返回 -1表示未找到。int main() { int dictionary[LEN] {1, 1, 2, 3, 5, 8, 13, 21, 34, 55}; int key 0; scanf(%d, key); int index BinarySearch(key, dictionary, LEN); if (index -1) { printf(Not found!\n); } else { printf(The index of %d is %d.\n, key, index); } return 0; }这段代码是我们的主函数。我们首先定义了一个有序字典dictionary其中存储了一些数字。然后通过scanf函数从用户输入中获取要搜索的关键字key。接下来我们调用了BinarySearch函数并将关键字、字典及其长度作为参数传递进去。得到的返回值存储在变量index中。最后我们根据index的值进行判断如果为 -1则输出 “Not found!”表示未找到关键字。否则我们输出关键字在字典中的索引。拓展内容有序字典的奇妙之处在本篇文章中我们提到了字典是有序的这是二分查找算法的前提条件之一。有序字典的优势何在呢有序字典可以大大提高查找效率因为我们可以通过比较关键字与中间元素的大小来确定应该继续搜索左半部分还是右半部分从而将查找范围一次次缩小直到找到目标元素。如果字典是无序的我们只能进行线性搜索效率将大大降低。避免使用全局变量我们在代码中看到了一个全局变量LEN它被用作字典的长度。尽管在这个简单的示例中使用全局变量不会带来太大问题但在实际开发中过多使用全局变量可能会导致代码不易读和维护。因此在设计程序时我们应尽量避免使用全局变量并且推荐将变量的作用范围限定在需要访问它的特定代码块内部。全局变量是在整个程序中都可以访问的变量而局部变量则只能在其定义的代码块中使用。在前述例子中LEN作为一个全局变量能够在整个代码中进行访问和修改。然而全局变量的广泛使用可能会导致代码复杂化和难以维护。当我们在大型项目或团队中开发软件时可能会有多个开发人员同时对代码进行修改和维护。过多使用全局变量会增加代码的耦合性使得多个部分的代码依赖于同一个变量。这样一来当我们需要修改全局变量时就需要仔细考虑它可能对其他代码的影响以免引发意想不到的错误和行为。为了解决这个问题我们可以尽量避免使用全局变量并将变量的作用范围限定在需要访问它的特定代码块内部。可以使用局部变量来替代全局变量并将其定义在需要使用的代码块中。这样一来每个代码块都拥有特定的上下文变量的作用范围也更加清晰明确。这种做法使得代码更容易理解和维护并且减少了潜在的冲突和错误。此外在设计和开发过程中我们还可以使用封装和模块化的原则将代码分成各个功能模块或类。每个模块或类都可以有自己的局部变量而不需要依赖于全局变量。这种结构化的设计可以提高代码的可读性和可维护性而且使得代码更易于重用和扩展。综上所述虽然在简单的情况下使用全局变量可能不会引起太大问题但在实际开发中过多使用全局变量可能会导致代码难以理解和维护。因此我们应该尽量避免使用全局变量并通过将变量的作用范围限定在需要访问它的特定代码块内部以提高代码的可读性、可维护性和可重用性。这样的设计原则和实践有助于构建更健壮、可靠且易于扩展的软件系统。