java代码实现二分算法深入简出

二分法

二分法，也称为二分查找法，是一种基于比较目标值和数组中间元素的查找算法。算法的思路是首先将整个数组的区间划分为左右两个子区间，然后通过比较目标值和中间元素的大小关系，确定目标值可能存在的子区间，从而缩小查找范围，直到找到目标值为止。

二分法算代码如下：

int binary_search(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = (right - left) / 2 + left;
        if (nums[mid] == target)
            return mid;
        else if (nums[mid] < target)
            left = mid + 1;
        else
            right = mid - 1;
    }
    return -1;  // 没有找到目标值
}

这个算法的关键在于 while 循环中的条件判断和更新左右边界的方法。具体步骤如下：

1. 定义两个指针 left 和 right，分别指向数组的首尾元素。

2. 在 while 循环中，判断 left 和 right 是否相交，如果相交了就退出循环，表示目标值不存在。

3. 计算中间位置 mid，更新 mid 方法为 (right - left) / 2 + left，防止 left 和 right 相加时溢出。

4. 比较 nums[mid] 和 target 的大小，如果 mid 对应的元素等于目标值，则返回 mid；否则，如果 mid 对应的元素小于目标值，则将 left 更新为 mid + 1，否则将 right 更新为 mid - 1。

5. 如果循环结束后还没有找到目标值，则返回 -1。

需要注意的是，二分法的前提条件是数组必须有序。如果数组无序，则需要先进行排序操作。此外，二分法还可以用来查找满足某个条件的最小或最大值，这时候需要结合具体问题进行具体分析。