数据结构与算法—二分查找(二)

用户3470542

发布于 2019-06-26 16:24:09

6690

发布于 2019-06-26 16:24:09

文章被收录于专栏：算法半岛算法半岛

二分查找的变形问题

学习完『数据结构与算法—二分查找（一）』后，接下来分析四种二分查找变形问题，对于每个问题分析时，我们都将数据从小到大排好序，如果数据从大到小排序，其解决思路是一致的。对于本次分析的从小到大排好序且有重复数组如下所示：

查找第一个值等于给定值的元素

当我们使用原来二分查找的方法查找第一个值等于给定值(18)的元素分析过程如下图所示：

从上图可以观察到，我们查找到的 nums[mid]=18却不是我们需要的第一个等于18的元素，因此使用原来的方法是无法处理这样的情况。下面我们分析下如何在有重复值的数组中查找第一个值等于给定值的元素，如下图所示：

相应的 java代码如下：

public int first(int[] nums, int n, int val){    int low = 0;        // low表示待查找区间的起始位置的下标    int high = n - 1;   // high表示待查找区间的终止位置的下标
    while(low <= high){        int mid = low + (high - low) / 2;   // mid表示待查找区间的中间位置的下标        if (nums[mid] < val){                          low = mid+1;        }else if(nums[mid] > val){                      high = mid - 1;        }else{                              // 当找到该数时，但需要判断是否为第一个            if (mid == 0 || nums[mid-1] != val) // 当mid为0时，说明元素已经是第一个，则返回；当nums[mid]的前一个数不为需要查找到数，则说明找到，则返回                return mid;            else                            // 不是第一个，则继续查找                high = mid-1;        }    }
    return -1;  // 当数字中没有需要查找的数，返回-1.}

查找最后一个值等于给定值的元素

分析了查找第一个值等于给定值的元素后再来分析查找最后一个值等于给定值的元素就简单了，基本思路差不多，下面来看看具体分析过程：

相应的 java代码如下：

public int second(int[] nums, int n, int val){    int low = 0;        // low表示待查找区间的起始位置的下标    int high = n - 1;   // high表示待查找区间的终止位置的下标
    while(low <= high){        int mid = low + (high - low) / 2;   // mid表示待查找区间的中间位置的下标        if (nums[mid] < val){            low = mid+1;        }else if(nums[mid] > val){            high = mid - 1;        }else{                              // 当找到该数时，但需要判断是否为最后一个            if (mid == n-1 || nums[mid+1] != val) // 当mid为n-1时，说明元素已经最后一个，则返回；当nums[mid]的后一个数不为需要查找到数，则说明找到，则返回                return mid;            else                            // 不是最后一个，则继续查找                low = mid+1;        }    }
    return -1;  // 当数字中没有需要查找的数，返回-1.}

查找第一个大于等于给定值的元素

分析完上两个后，对于查找第一个大于等于给定值的元素的分析过程也差不多，这里就不画图，其代码如下所示：

public int third(int[] nums, int n, int val){    int low = 0;        // low表示待查找区间的起始位置的下标    int high = n - 1;   // high表示待查找区间的终止位置的下标
    while(low <= high){        int mid = low + (high - low) / 2;   // mid表示待查找区间的中间位置的下标        if (nums[mid] < val){            low = mid+1;        }else if(nums[mid] >= val){    // 当找到符合条件的数时，但需要判断是否为第一个            if (mid == 0 || nums[mid-1] < val) // 当mid为0时，说明已经是第一个，则返回；当nums[mid]的前一个数不符合查找条件时，则说明找到，则返回                return mid;            else                            // 不是第一个，则继续查找                high = mid-1;        }    }
    return -1;  // 当数字中没有需要查找的数，返回-1.}

查找最后一个小于等于给定值的元素

对于查找最后一个小于等于给定值的元素的分析过程也差不多，直接给出代码，如下所示：

public int four(int[] nums, int n, int val){    int low = 0;        // low表示待查找区间的起始位置的下标    int high = n - 1;   // high表示待查找区间的终止位置的下标
    while(low <= high){        int mid = low + (high - low) / 2;   // mid表示待查找区间的中间位置的下标
        if (nums[mid] <= val){            if (mid == n-1 || nums[mid+1] > val) // 当mid为n-1时，说明元素已经最后一个，则返回；当nums[mid]的后一个数不为需要查找到数，则说明找到，则返回                return mid;            else                            // 不是最后一个，则继续查找                low = mid+1;        }else if(nums[mid] > val){            high = mid - 1;        }    }
    return -1;  // 当数字中没有需要查找的数，返回-1.}

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2019-06-16，如有侵权请联系 cloudcommunity@tencent.com 删除

java