12. 二分搜索

PangHu大约 6 分钟

二分搜索（Binary Search）是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。

实现原理

首先，从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束。
如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。
如果在某一步骤数组为空，则代表找不到。

一步步数据演示

假设我们有一个已排序的整数数组[1, 3, 5, 7, 9]，我们想在其中搜索数字5。

从数组的中间元素开始，即5（索引为2）。
将5与目标值5进行比较，发现它们相等，因此搜索过程结束，返回索引2。

如果我们想搜索数字6，则：

从数组的中间元素开始，即5（索引为2）。
将5与目标值6进行比较，发现5小于6，因此我们在数组的右半部分（即[7, 9]）继续搜索。
此时，右半部分的中间元素是7（索引为3）。
将7与目标值6进行比较，发现7大于6，因此我们在右半部分的左半部分（即[7]）继续搜索。但此时数组只有一个元素且不等于目标值，所以搜索失败，返回-1。

二分搜索（Binary Search）作为一种高效的搜索算法，在有序数组中查找特定元素时具有显著的优势，但同时也存在一些局限性。以下是二分搜索的优缺点：

优点：

高效的时间复杂度：二分搜索的时间复杂度为O(log n)，其中n是数组的长度。这意味着在大型有序数组中，二分搜索可以显著减少搜索时间，比线性搜索（O(n)）要快得多。
易于实现：二分搜索的算法逻辑相对简单，易于理解和实现。
对数组中的元素进行排序不改变其相对顺序：由于二分搜索是基于比较的搜索算法，它不会改变数组中元素的相对顺序。
适用于静态数据集：如果数据集在搜索过程中不会改变，那么二分搜索是一个很好的选择。

缺点：

要求数据有序：二分搜索要求数据必须是有序的。如果数据集无序，需要先进行排序，这可能会增加额外的计算成本。
无法处理动态数据集：如果数据集在搜索过程中会发生变化（如插入或删除元素），那么二分搜索可能不是最佳选择。在这种情况下，可能需要使用其他数据结构（如平衡二叉搜索树）来维护有序性并允许动态更新。
无法处理非数组数据结构：二分搜索通常适用于数组或类似数组的数据结构。对于链表、树或其他非数组数据结构，可能需要将其转换为数组或采用其他搜索算法。
空间复杂度：虽然二分搜索本身的空间复杂度为O(1)（只需要常数级别的额外空间），但如果需要对无序数据集进行排序以应用二分搜索，则排序过程可能需要额外的空间（具体取决于所使用的排序算法）。
插入和删除操作复杂度高：二分搜索本身不直接支持插入和删除操作。如果需要在有序数组中插入或删除元素，可能需要先找到插入或删除的位置，然后执行相应的操作，这可能会导致较高的时间复杂度。相比之下，平衡二叉搜索树等数据结构可以在O(log n)时间复杂度内执行插入、删除和搜索操作。

使用场景

二分搜索（Binary Search）是一种非常高效的搜索算法，尤其适用于在有序数组中查找特定元素。以下是二分搜索的一些常见使用场景：

有序数组搜索：当需要在有序数组中查找某个元素时，二分搜索是最佳选择。它利用数组的有序性，通过不断缩小搜索范围来快速定位目标元素。
数据库索引：在数据库中，为了加快查询速度，经常会对某些字段建立索引。这些索引通常是有序的，因此可以使用二分搜索来快速定位到满足查询条件的记录。
文件搜索：在有序文件中查找特定信息时，可以使用二分搜索来快速定位到目标位置。例如，在字典或电话号码簿中查找某个单词或电话号码时，可以利用二分搜索来快速定位到相应的页码或条目。
竞争编程：在编程竞赛中，经常需要处理大量数据并快速给出结果。二分搜索作为一种高效的搜索算法，经常被用于解决各种问题，如排序、查找、计算最值等。
数据结构和算法实现：二分搜索是许多数据结构和算法的基础，如平衡二叉搜索树（AVL树、红黑树等）、堆排序、归并排序等。在实现这些数据结构和算法时，可能需要使用到二分搜索的思想和技巧。
科学计算和数据分析：在科学计算和数据分析中，经常需要处理大量有序数据。二分搜索可以帮助我们快速定位到感兴趣的数据点，从而进行进一步的分析和处理。

需要注意的是，虽然二分搜索在有序数组中非常高效，但它也有一些限制。例如，它要求数据必须是有序的；如果数据无序，需要先进行排序才能使用二分搜索。此外，二分搜索只能用于一维数组或线性结构，对于多维数组或树形结构等复杂数据结构，可能需要使用其他搜索算法或数据结构来实现高效搜索。

Java代码示例

public class BinarySearch { 
    public static void main(String[] args) { 
        int[] array = {1, 3, 5, 7, 9}; 
        int target = 5; 
        int index = binarySearch(array, target); 
           
        if (index != -1) { 
            System.out.println("目标值 " + target + " 在数组中的索引是: " + index); 
        } else { 
            System.out.println("目标值 " + target + " 不在数组中"); 
        } 
    } 
   
    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; // 未找到目标值 
    } 
}

当你运行上面的Java代码时，它将输出：目标值 5 在数组中的索引是: 2。