折半查找算法在顺序存储和链式存储的数据结构中应用有何不同？请描述其在两种存储结构下的步骤和时间复杂度。

折半查找算法是一种在有序数组中实现快速查找的方法，其基本思想是将目标值与数组中间元素进行比较，并根据比较结果缩小搜索范围的一半。在顺序存储结构（如数组）中，折半查找的步骤和时间复杂度表现得非常明显，而在链式存储结构（如链表）中则存在一定的局限性。

参考资源链接：[折半查找算法详解：步骤、数据结构与时间复杂度](https://wenku.csdn.net/doc/6fp47hj3d5?spm=1055.2569.3001.10343)

首先，我们来看顺序存储结构，通常也就是数组。在数组中实施折半查找，有以下步骤：

1. 设置查找区间：初始情况下，low = 0，high = n-1，其中n是数组的长度。
2. 计算中间位置：mid = (low + high) / 2。
3. 比较和调整区间：如果arr[mid] > key，则high = mid - 1；如果arr[mid] < key，则low = mid + 1；如果arr[mid] == key，则查找成功。
4. 查找成功与失败：重复上述步骤直到low > high，表示查找失败。

在顺序存储结构中，折半查找的时间复杂度是O(log n)，因为每次查找都将区间缩小一半。

然而，在链式存储结构中，折半查找的实现变得复杂。链表不支持随机访问，因此无法直接通过索引访问中间元素，这会增加获取中间元素的时间复杂度。此外，每次需要移动到前驱或后继节点以调整查找范围，这使得链表实现的折半查找的时间复杂度实际上退化为O(n)。

总结来说，尽管折半查找在逻辑上适用于链表，但由于链表的特性，它并不是链表数据结构中的理想查找算法。在顺序存储结构中，折半查找的效率高，时间复杂度低，而在链式存储结构中，折半查找则不适用，更适合采用其他查找方法，如线性查找。

对于希望深入理解并应用折半查找的读者，建议阅读《折半查找算法详解：步骤、数据结构与时间复杂度》一书。本书不仅详细解释了折半查找的原理和步骤，还探讨了它与不同数据结构的结合及其时间复杂度分析，非常适合希望提高数据结构和算法知识水平的读者。

参考资源链接：[折半查找算法详解：步骤、数据结构与时间复杂度](https://wenku.csdn.net/doc/6fp47hj3d5?spm=1055.2569.3001.10343)