Java教程

二分基础

本文主要是介绍二分基础,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

二分查找实际上就是采用了分治法的思想

以下模板都以升序数组为准

模板一: 标准的二分查找

场景:数组元素有序且不重复

有的话返回索引,没有返回-1

int binarySearch(vector<int>& arr, int target) {
    int left = 0, right = nums.size() - 1;
    
    while (left <= right) {//<=指可以取到右区间,是[left,right]
        int mid = left + ((right - left) >> 1);
        if (nums[mid] == target) return mid;
        else if (nums[mid] > target) right = mid - 1;//证明target可能在mid左侧
        else left = mid + 1;//证明nums[mid] < target, target可能在mid右侧
    }
    
    return -1;
}

模板二:二分查找找边界

二分查找左/有边界是二分查找的变式,一般有如下场景:

1)第一种情况

  • 数组总体有序,包含重复元素
  • 数组部分有序,且不包含重复元素

2)第二种情况

  • 数组部分有序,且包含重复元素

二分查找找左边界

1)针对第一种情况:

int binarySearch(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    
    while (left < right) {//这是左闭右开[,),不包含最后一个数,left = right 的时候会跳出
        int mid = left + ((right - left) >> 1);
        if (nums[mid] < targrt) left = mid + 1;
        else right = mid;//nums[mid] >= target, 都需要往左边收缩边界(主要)
    }
    //因为里面是没有判断left = right 这个索引的位置,需要打个补丁
    return nums[left] == target ? left : -1;
}

2)针对第二种情况(模板有误)


二分查找找右边界

1)针对第一种情况

int binarySearch(vector<int>& nums, int target) {
	int left = 0, right = nums.size() - 1;
    int mid;
    
    while (left < right) {
        mid = left + ((right - left) >> 1) + 1;//需要注意,这里多加了个1,这样无论是奇偶数,中间位置都偏右,这样避免了死循环(如果不加1,比如{2,2}就会死循环
        if (nums[mid] > target) right = mid - 1;//收缩右边界
        else left = mid;//numd[mid] <= target,都需要收缩左边界(主要)
    }
    //打个补丁,这里写左右都可以
    return nums[left] == target ? left : -1;
}

2)针对第二种情况


二分查找找左右边界

分别查找左右边界即可

1)第一种情况

vector<int> searchRange(vector<int>& nums, int target) {
    vector<int> res{-1,-1};//res[0]存左边界,res[1]存右边界
    
    int left = 0, right = nums.size() - 1;
    int mid;
    
    while (left < right) {//先找左边边界
        mid = left + ((right - left) >> 1);
        if (nums[mid] < target) left  = mid + 1;
        else right = mid;
    }
    res[0] = nums[left] == target ? left : -1;
    
    if (res[0] != -1) {//存在左边边界查找右边边界
        if (left == nums.size() - 1 || nums[left + 1] != target) {//可能只有一个target,它的位置可能在末尾/其他位置
            res[1] = left;
        }
        else {//有多个target
            right = nums.size() - 1;
            
            while (left < right) {
                mid = left + ((right - left) >> 1) + 1;
                if (nums[mid] > target) right = mid - 1;
                else left = mid;
            }
            res[1] = nums[left] == target ? left : -1;
        }
    }
    
    return res;
}

模板三:二分查找找极值点

二分查找的一种变式:找极值,即是v或者^的最值点;

我们查找的时候不再是和target进行比较,而是和相邻元素比较,以达到某种单调区间检测的效果

下面以查找^的极值点写一个模板:

int binarySearch(vector<int>& nums) {
    int left = 0, right = nums.size() - 1;
    int mid;
    
    while (left <= right) {
       mid = left + ((right - left) >> 1);
       
        if (nums[mid] > nums[mid] + 1 && nums[mid] > nums[mid - 1]) return mid;
        else if (nums[mid] > nums[mid + 1]) right = mid - 1;//极值点在左边
        else left = mid + 1;//极值点在右边
    }
    
    return -1;
}
这篇关于二分基础的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!