二分查找算法

文章目录

二分查找
二分的实战+讲解
- 二分查找
- - 普通二分模版
- 在排序数组中查找元素的第一个和最后一个位置
- - 万能二分模版
总结

二分查找

什么是二分查找:就是定义左右2个指针(此指针非真指针)取中间值
通过一次次取中间值找到要找到的数

二分的实战+讲解

二分查找

题目:地址

题目解析:
在这里插入图片描述

找到一个等于target的值
并返回他的下标
题目中给的数组是升序的

题目讲解

这样就能找到要找的目标值
如果没有找到那么就可以返回-1

代码:

class Solution {
public:
    int search(vector<int>& nums, int target) 
    {
        int left = 0,right =nums.size()-1,sum = 0;
        while(left<=right)
        {
            sum = left+(right-left+1)/2;//这里的+1要不要无所谓在这个题
            if(nums[sum]<target)
            {
                left=sum+1;
            }
            else if (nums[sum]>target)
            {
                right = sum-1;
            }
            else
            {
                return sum;
            }
        }
        return -1;
    }
};

普通二分模版

在这里插入图片描述

在排序数组中查找元素的第一个和最后一个位置

题目:地址

题目解析:

找到等于target的第一个下标和最后一个下标
并且返回
数组是升序的

题目讲解

代码:

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) 
    {
        if(nums.size()==0)
        {
            return {-1,-1};
        }
        int left=0,right=nums.size()-1;
        int mid = 0;
        int begin = 0,end = 0;
        while(left<right)
        //找左端点
        //不能写等于
        //因为写了等于会死循环
        //right位置不改变
        //mid位置会永远不动
        {
            //这里的不能写成right-left+1的形式
            //如果写了会出现死循环
            //同样的 right位置不改变
            //mid也不会动 进而死循环
            mid = left+(right-left)/2;
            if(nums[mid]>=target)
            {
                right=mid;
            }
            else
            {
                left=mid+1;
            }
        }
        if(nums[left]==target)
        {
            begin=left;
        }
        else
        {
            return {-1,-1};
        }
        right=nums.size()-1;
        while(left<right)
        {
            //这里的不能写成right-left的形式
            //如果写了会出现死循环
            //同样的 left位置不改变
            //mid也不会动 进而死循环
            mid = left+(right-left+1)/2;
            if(nums[mid]>target)
            {
                right=mid-1;
            }
            else
            {
                left=mid;
            }
        }
        end = right;
        return {begin,end};
    }
};