二分法相关使用

1. 在一个有序数组中,找某个数是否存在

在线OJ：704. 二分查找

有序数组下的二分思路如下:

• 由于这里是有序数组, 我们可以可以先得到中点位置, 中点可以把数组分为左右两边;
• 如果中点位置的值等于目标值, 直接返回中点位置;
• 如果中点位置的值小于目标值, 则去数组中点左侧按同样的方式查找;
• 如果中点位置的值大于目标值, 则取数组中点右侧按同样的方式查找；
• 如果最后没有找到, 则返回 -1.

代码实现如下:

class Solution {
    public int search(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        int left = 0;
        int right = nums.length - 1;
        int mid = 0;
        while (left < right) {
            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;
    }
}

2. 在一个有序数组中,找大于等于某个数最左侧的位置

在线OJ: 35. 搜索插入位置

通过题目示例可以知道, 这个题本质上就是在一个有序数组中, 找大于等于某个数最左侧的位置, 如果不存在, 就返回数组长度 (表示插入在最末尾位置).

这个题只需要在 1 代码基础上进行简单改动即可, 在 1 中, 我们找到满足条件的位置就直接返回了; 而在本题中, 因为要找到最左侧的位置, 所以, 在遇到 nums[mid] >= target 的时候, 不用直接返回, 而是先把位置 mid 记录下来, 然后继续去左侧找是否还有满足条件的更左边的位置.

代码实现如下:

class Solution {
    public int searchInsert(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        int left = 0;
        int right = nums.length - 1;
        int mid = 0;
        int ans = nums.length;
        while (left <= right) {
            mid = left + (right - left) / 2;
            if (nums[mid] >= target) {
                ans = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }
}

3. 在一个有序数组中, 找小于等于某个数最右侧的位置

和 2 的实现基本是一样的, 就不赘述了, 代码如下:

/**
 * 有序数组中找到 <=num 最右的位置
 */
public static int mostRightIndex(int[] arr, int num) {
    if (arr == null || arr.length == 0) {
        return -1;
    }
    int left = 0;
    int right = arr.length - 1;
    int mid = 0;
    int ans = -1;
    while (left <= right) {
        mid = left + (right - left) / 2;
        if (arr[mid] <= num) {
            ans = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return ans;
}

4. 局部最大值问题

在线OJ：162. 寻找峰值

思路如下:

题目中已经说明, 对于所有有效的 i 都有nums[i] != nums[i + 1], 所以, 不会出现相邻相等的情况.

假设数组长度为 N, 首先判断 0 号位置的数和 N-1 号位置的数是不是峰值位置; 0 号位置只需要和 1 号位置比较, 如果 0 号位置大; 0 号位置就是峰值位置 (0 号位置位置左边没有元素, 可以认为是无穷小), 可以直接返回.

N-1 号位置只需要和 N-2 号位置比较, 如果 N-1 号位置大, N-1 号位置就是峰值位置 (N-1 号位置右边没有元素, 可以认为是无穷大), 可以直接返回.

如果 0 号位置和 N-1 在上轮比较中均是最小值, 那么数组的样子必然是如下情况:

由上图可知, 0 到 1 这段是增长趋势, N-2 到 N-1 这段是下降趋势, 那么峰值位置必在[1…N-2]之间出现;

此时可以通过二分来找峰值位置, 先来到中点位置, 假设中点为 mid, 如果中点位置的值比左右两边的值都大, 即:

arr[mid] > arr[mid+1] && arr[mid] > arr[mid-1]

则 mid 位置就是峰值位置, 直接返回即可.

否则, 有如下两种情况:

• 情况一, mid 位置的值比 mid - 1 位置的值小, 趋势如下图, 此时可以在[1...(mid-1)]区间内继续二分;

• 情况二, mid 位置的值比 mid + 1 位置的值小, 趋势如下图, 此时可以在[(mid+1)...(N-2)]区间内继续二分;

如果最后都没找到, 返回 -1 即可.

代码实现如下:

class Solution {
    public int findPeakElement(int[] arr) {
        int len = arr.length;
        if (arr == null || len == 0) {
            return -1;
        }
        if (len == 1) {
            return 0;
        }
        if (arr[0] > arr[1]) {
            return 0;
        }
        if (arr[len - 1] > arr[len - 2]) {
            return len - 1;
        }

        int left = 1;
        int right = len - 2;
        int mid= 0;
        while (left <= right) {
            mid = left + (right-left) / 2;
            if (arr[mid] > arr[mid-1] && arr[mid] > arr[mid + 1]) {
                return mid;
            }
            if (arr[mid] < arr[mid - 1]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return -1;
    }
}

补充一下如果想要实现找局部最小值的话, 思路是一样的, 把代码符号改改就行了, 代码如下:

/**
 * 局部最小值问题
 * arr数组中的元素直接一定是相邻不相等的元素
 * 可以是无序的
 */
// 返回任意一个局部最小值即可
public static int oneMinIndex(int[] arr) {
    int len = arr.length;
    if (arr == null || len == 0) {
        return -1;
    }
    if (len == 1) {
        return 0;
    }
    if (arr[0] < arr[1]) {
        return 0;
    }
    if (arr[len - 1] < arr[len - 2]) {
        return len - 1;
    }

    int left = 1;
    int right = len - 2;
    int mid= 0;
    while (left <= right) {
        mid = (left + right) / 2;
        if (arr[mid] > arr[mid - 1]) {
            right = mid - 1;
        } else if (arr[mid] > arr[mid + 1]) {
            left = mid + 1;
        } else {
            return mid;
        }
    }
    
    return -1;
}