目录

以下是二分查找的详细步骤：

初始化左右边界：将初始查找范围设置为整个数组，即left = 0，right = array.length - 1。

计算中间元素的索引：mid = (left + right) / 2。

检查中间元素是否是目标元素：

重复步骤2和步骤3，直到找到目标元素或左边界大于右边界

代码

 我的其他博客

---

---

二分查找，也称为折半查找，是一种在有序数组中查找特定元素的高效算法。其基本思想是每次将查找范围缩小一半，直到找到目标元素或确定目标元素不存在。

以下是二分查找的详细步骤：

1. 初始化左右边界：将初始查找范围设置为整个数组，即left = 0，right = array.length - 1。

2. 计算中间元素的索引：mid = (left + right) / 2。

3. 检查中间元素是否是目标元素：

   • 如果 array[mid] == target，则找到目标元素，返回 mid。
   • 如果 array[mid] < target，说明目标元素在右半部分，更新 left = mid + 1。
   • 如果 array[mid] > target，说明目标元素在左半部分，更新 right = mid - 1。

4. 重复步骤2和步骤3，直到找到目标元素或左边界大于右边界

代码

public class BinarySearch {
    // 二分查找函数
    public static int binarySearch(int[] array, int target) {
        int left = 0;
        int right = array.length - 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;
    }

    public static void main(String[] args) {
        int[] array = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        int target = 7;

        int result = binarySearch(array, target);

        if (result != -1) {
            System.out.println("目标元素 " + target + " 在数组中的索引为 " + result);
        } else {
            System.out.println("目标元素 " + target + " 不存在于数组中");
        }
    }
}

这段代码演示了如何使用二分查找在有序数组中查找目标元素。在 main 方法中，我们定义了一个有序数组 array，并在其中查找目标元素 target。最后输出结果，指示目标元素是否存在以及其索引位置。 

优缺点

优点：

1. 时间复杂度低： 二分查找的时间复杂度是 O(log n)，相比线性搜索 O(n)，在大型有序数据集上具有更高的效率。

2. 简单清晰： 算法逻辑相对简单，易于理解和实现。

3. 节省空间： 二分查找通常只需要很少的额外空间，主要用于存储左右边界、中间索引等变量。

缺点：

1. 仅适用于有序数据： 二分查找要求数据集是有序的，如果数据集无序，需要先进行排序，这可能增加额外的时间复杂度。

2. 不适用于链表： 二分查找需要随机访问，对于链表这样的数据结构，二分查找的效率较低，因为它无法直接跳到中间元素。

3. 只能查找单一元素： 二分查找适用于查找单一元素的情况，如果需要查找多个匹配的元素，可能需要其他算法。

4. 不适用于动态数据集： 如果数据集经常发生变化，频繁的插入和删除可能会导致数组重新排序，使得二分查找的优势减弱。

总体来说，二分查找是一种非常有用的算法，尤其适用于有序数据集的查找操作。然而，使用前需要考虑数据集的特点和操作需求，以确保选择最适合的算法。

其他的用途

在实际应用中，二分查找常常用于：

1. 搜索： 在有序数组中快速查找某个元素的索引。
2. 算法优化： 在某些算法中，通过二分查找可以提高搜索效率，例如在分治算法中。
3. 数据库操作： 在数据库索引的查找过程中，二分查找也有着广泛的应用。
4. 游戏开发： 在有序数组或有序集合中查找元素，如查找排行榜中的玩家。

总体来说，二分查找在需要高效搜索有序数据集的情况下是非常有用的。

与他类似的查找

1. 线性查找（Linear Search）：

   • 特点： 顺序遍历数据集，逐个比较元素，直到找到目标或遍历完整个数据集。
   • 适用场景： 数据集无序或未排序，或者需要查找的元素在数据集中的位置相对较靠前。

2. 哈希查找（Hashing）：

   • 特点： 使用哈希函数将元素映射到一个索引，快速定位元素。
   • 适用场景： 适用于需要快速查找、插入和删除的情况，但要求数据结构具有哈希函数的支持。

3. 插值查找（Interpolation Search）：

   • 特点： 根据目标值的估计位置进行查找，适用于有序且均匀分布的数据集。
   • 适用场景： 数据集有序且均匀分布时，插值查找可能比二分查找更快。

4. 树结构查找（二叉搜索树、平衡二叉搜索树、B 树等）：

   • 特点： 使用树结构进行有序数据的查找，支持高效的查找、插入和删除操作。
   • 适用场景： 适用于需要频繁的插入和删除操作，同时要求有序性的数据集。

5. 线性索引查找（例如块索引）：

   • 特点： 使用索引结构，将数据集分块，通过索引快速定位块，然后再在块内进行查找。
   • 适用场景： 适用于大型数据集，其中块的数量相对较小，但每个块中的元素数量较大。

 我的其他博客

HTTP与HTTTPS的区别-程序员宅基地

什么情况下会产生StackOverflowError（栈溢出）和OutOfMemoryError（堆溢出）怎么排查-程序员宅基地

谈谈我对HashMap扩容机制的理解及底层实现-程序员宅基地