深入理解【二分法】：从基础概念到实际应用

二分法

｜｜在 Java 中，二分法（Binary Search）是一种高效的查找算法，通常用于在有序数据集（如数组或列表）中快速定位目标元素。它的核心思想是将搜索范围不断缩小一半，从而达到 O(log n) 的时间复杂度。根据应用场景和实现方式，二分法可以分为几种常见的分类。以下是二分法的分类及其对应的例子。

一、二分法分类

1. 标准二分查找（Standard Binary Search）

• 描述: 在有序数组中查找特定目标值的精确位置。
• 适用场景: 数组已排序，需要找到目标值是否存在及其索引。
• 时间复杂度: O(log n)。

示例代码

public class BinarySearch {
    public static int binarySearch(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2; // 避免溢出
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1; // 未找到
    }

    public static void main(String[] args) {
        int[] nums = {2, 3, 4, 10, 40};
        int target = 10;
        int result = binarySearch(nums, target);
        System.out.println("目标索引: " + result); // 输出 3
    }
}

2. 查找第一个或最后一个位置（Find First or Last Occurrence）

• 描述: 在有序数组中查找目标值的第一个出现位置或最后一个出现位置（适用于有重复元素的情况）。
• 适用场景: 需要定位重复元素的边界。
• 时间复杂度: O(log n)。

示例代码

public class FindFirstAndLast {
    // 查找第一个出现的位置
    public static int findFirst(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int result = -1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                result = mid; // 记录可能的结果
                right = mid - 1; // 继续向左寻找
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return result;
    }

    // 查找最后一个出现的位置
    public static int findLast(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int result = -1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                result = mid; // 记录可能的结果
                left = mid + 1; // 继续向右寻找
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[] nums = {5, 7, 7, 8, 8, 10};
        int target = 8;
        System.out.println("第一个位置: " + findFirst(nums, target)); // 输出 3
        System.out.println("最后一个位置: " + findLast(nums, target)); // 输出 4
    }
}

3. 查找插入位置（Search Insert Position）

• 描述: 在有序数组中查找目标值的插入位置（如果目标不存在，返回它应该插入的位置）。
• 适用场景: 数组已排序，需要确定目标的逻辑位置。
• 时间复杂度: O(log n)。

示例代码

public class SearchInsertPosition {
    public static int searchInsert(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return left; // left 是插入位置
    }

    public static void main(String[] args) {
        int[] nums = {1, 3, 5, 6};
        int target = 2;
        System.out.println("插入位置: " + searchInsert(nums, target)); // 输出 1
    }
}

4. 基于条件的二分查找（Binary Search with Condition）

• 描述: 不直接查找具体值，而是根据某种条件（如单调性）将问题转化为二分查找。
• 适用场景: 解决非直接查找的问题，如寻找峰值、最小值或满足条件的边界。
• 时间复杂度: O(log n)。

示例代码

public class FindPeakElement {
    public static int findPeakElement(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > nums[mid + 1]) { // 峰值在左侧（包括 mid）
                right = mid;
            } else { // 峰值在右侧
                left = mid + 1;
            }
        }
        return left; // left 是峰值索引
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 1};
        System.out.println("峰值索引: " + findPeakElement(nums)); // 输出 2
    }
}

5. 旋转数组的二分查找（Binary Search in Rotated Sorted Array）

• 描述: 在旋转后的有序数组中查找目标值，数组原本有序但被旋转了未知次数。
• 适用场景: 处理旋转数组中的查找问题。
• 时间复杂度: O(log n)。

示例代码

public class SearchInRotatedSortedArray {
    public static int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            
            // 判断哪一半是有序的
            if (nums[left] <= nums[mid]) { // 左半部分有序
                if (nums[left] <= target && target < nums[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } else { // 右半部分有序
                if (nums[mid] < target && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }
        return -1; // 未找到
    }

    public static void main(String[] args) {
        int[] nums = {4, 5, 6, 7, 0, 1, 2};
        int target = 0;
        System.out.println("目标索引: " + search(nums, target)); // 输出 4
    }
}

总结

二分法的关键在于利用数据的有序性或单调性，通过不断缩小搜索范围来提高效率。以上例子展示了二分法在不同场景下的应用。如果需要更深入的解释或更多例子，请告诉我！

二、区间临界值取值思路

二分查找涉及的很多的边界条件，逻辑比较简单，但就是写不好。例如到底是 while(left < right) 还是 while(left <= right)，到底是right = middle呢，还是要right = middle - 1呢？

大家写二分法经常写乱，主要是因为对区间的定义没有想清楚，区间的定义就是不变量。要在二分查找的过程中，保持不变量，就是在while寻找中每一次边界的处理都要坚持根据区间的定义来操作，这就是循环不变量规则。

写二分法，区间的定义一般为两种，左闭右闭即[left, right]，或者左闭右开即[left, right)。

三、二分法表示方法

迭代、递归 和 Java 中的 Arrays.binarySearch。这三种方式都可以实现二分查找的功能，只是实现方式和使用场景有所不同。以下我会详细讲解这三种形式，并为每种形式提供具体的 Java 示例。

1. 迭代形式（Iterative Binary Search）

• 描述: 使用循环（通常是 while 循环）来不断缩小搜索范围，直到找到目标或确定目标不存在。
• 优点: 空间复杂度低（O(1)），不需要额外的栈空间。
• 适用场景: 适合大多数二分查找问题，尤其是性能敏感的场景。

示例代码

public class IterativeBinarySearch {
    public static int binarySearch(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2; // 避免溢出
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1; // 未找到
    }

    public static void main(String[] args) {
        int[] nums = {2, 3, 4, 10, 40};
        int target = 10;
        int result = binarySearch(nums, target);
        System.out.println("目标索引: " + result); // 输出 3
    }
}

2. 递归形式（Recursive Binary Search）

• 描述: 通过递归调用函数来实现二分查找，每次递归将问题规模减半。
• 优点: 代码逻辑清晰，容易理解。
• 缺点: 空间复杂度较高（O(log n)），因为递归调用会占用栈空间。
• 适用场景: 适合教学或代码结构要求递归的场景。

示例代码

public class RecursiveBinarySearch {
    public static int binarySearch(int[] nums, int target, int left, int right) {
        if (left > right) {
            return -1; // 未找到
        }
        
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] < target) {
            return binarySearch(nums, target, mid + 1, right); // 递归右半部分
        } else {
            return binarySearch(nums, target, left, mid - 1);   // 递归左半部分
        }
    }

    public static void main(String[] args) {
        int[] nums = {2, 3, 4, 10, 40};
        int target = 10;
        int result = binarySearch(nums, target, 0, nums.length - 1);
        System.out.println("目标索引: " + result); // 输出 3
    }
}

3. Arrays.binarySearch（Java 内置方法）

• 描述: Java 提供了一个内置的二分查找方法 Arrays.binarySearch，适用于有序数组。它返回目标值的索引，如果未找到则返回负值（具体为 -(插入点) - 1）。
• 优点: 简单易用，无需手动实现。
• 缺点: 功能较为固定，不够灵活，无法轻易修改逻辑。
• 适用场景: 快速开发或标准二分查找需求。

示例代码

import java.util.Arrays;

public class ArraysBinarySearch {
    public static void main(String[] args) {
        int[] nums = {2, 3, 4, 10, 40};
        int target = 10;
        
        int result = Arrays.binarySearch(nums, target);
        if (result >= 0) {
            System.out.println("目标索引: " + result); // 输出 3
        } else {
            System.out.println("未找到，插入点: " + (-result - 1)); // 如果未找到
        }

        // 测试未找到的情况
        target = 5;
        result = Arrays.binarySearch(nums, target);
        System.out.println("未找到，插入点: " + (-result - 1)); // 输出 3
    }
}

三种形式的对比

注意事项

1. 前提条件: 无论哪种形式，二分查找都要求输入数组是有序的。如果数组未排序，需要先排序（例如使用 Arrays.sort()）。
2. 边界处理: 在迭代和递归实现中，注意 left <= right（而不是 <），以确保不会遗漏边界元素。
3. 溢出问题: 计算中间索引时，使用 left + (right - left) / 2 而不是 (left + right) / 2，以防止整数溢出。

希望这些示例和说明能帮你更好地理解二分法的三种表示形式！