【LeetCode 01】二分查找总结

简介: 【LeetCode 01】二分查找总结

一、适用条件

二分查找适用条件为:

  • 数组问题
  • 有序无重复元素数组

如【LeetCode 704】:给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。

二、方法类型

二分查找法的思路主要是根据区间定义的“不变量”进行划分的。二分法中区间的定义主要有两种:

  1. 左闭右闭[left,right]
    意思是target值在区间[left,right]中,那么left与right的关系是 “<=”
while(left<=right){
    xxxx;
}
  1. 左闭右开[left,right)
    意思是target值在区间[left,right)中,那么left与right的关系是“<”
while(left<right){
    xxx;
}

三、二分法的两种写法

根据例题:

3.1第一种写法“左闭右闭”

int search(int* nums, int numsSize, int target){
    //step1:写出临界条件变量:left,right
    int left=0;
    int right=numSize-1;
    //------------------------
    
    //step2:写出区间--左闭右闭;写出middle动态值
    while(left<=right){
        int middle=left+((right-left)/2);//数组取中间值赋给middle变量
        //step3:根据条件移动middle值
        if(nums[middle]>target){
            //step4:往条件里补充条件(left,right指针如何动态移动?)
             right=middle-1;
        }else if(nums[middle<target]){
            left=middle+1
        }else{
            return middle;//找到目标值target=middle
        }
    }
    return -1;
    
}

3.2第二种写法“左闭右开”

int search(int* nums, int numsSize, int target){
    //step1:写出临界条件变量:left,right
    int left=0;
    int right=numSize-1;
    //------------------------
    
    //step2:写出区间--左闭右闭;写出middle动态值
    while(left<right){
        int middle=left+((right-left)/2);//数组取中间值赋给middle变量
        //step3:根据条件移动middle值
        if(nums[middle]>target){
            //step4:往条件里补充条件(left,right指针如何动态移动?)
             right=middle;
        }else if(nums[middle<target]){
            left=middle+1
        }else{
            return middle;//找到目标值target=middle
        }
    }
    return -1;
    
}
return middle;//找到目标值target=middle
    }
}
return -1;

}

目录
相关文章
|
7月前
leetcode:374. 猜数字大小(二分查找)
leetcode:374. 猜数字大小(二分查找)
39 0
|
7月前
|
算法 测试技术 C#
【二分查找】【区间合并】LeetCode2589:完成所有任务的最少时间
【二分查找】【区间合并】LeetCode2589:完成所有任务的最少时间
|
4月前
|
Python
【Leetcode刷题Python】704. 二分查找
解决LeetCode "二分查找" 问题的Python实现代码。
20 0
|
4月前
|
算法 索引 Python
【Leetcode刷题Python】34. 在排序数组中查找元素的第一个和最后一个位置(二分查找)
解决LeetCode "在排序数组中查找元素的第一个和最后一个位置" 问题的方法。第一种方法是使用两次二分查找,首先找到目标值的最左边界,然后找到最右边界。第二种方法是利用Python的list.index()方法,先正序找到起始位置,再逆序找到结束位置,并给出了两种方法的Python实现代码。
63 0
|
6月前
|
索引
【LeetCode刷题】二分查找:山脉数组的峰顶索引、寻找峰值
【LeetCode刷题】二分查找:山脉数组的峰顶索引、寻找峰值
|
6月前
【LeetCode刷题】专题三:二分查找模板
【LeetCode刷题】专题三:二分查找模板
【LeetCode刷题】专题三:二分查找模板
|
6月前
|
算法 数据可视化 数据挖掘
深入解析力扣162题:寻找峰值(线性扫描与二分查找详解)
深入解析力扣162题:寻找峰值(线性扫描与二分查找详解)
|
7月前
|
算法 索引
【数据结构与算法 | 基础篇】力扣704/35/34:二分查找
【数据结构与算法 | 基础篇】力扣704/35/34:二分查找
|
6月前
【LeetCode刷题】二分查找:寻找旋转排序数组中的最小值、点名
【LeetCode刷题】二分查找:寻找旋转排序数组中的最小值、点名
|
6月前
|
算法
【经典LeetCode算法题目专栏分类】【第6期】二分查找系列:x的平方根、有效完全平方数、搜索二位矩阵、寻找旋转排序数组最小值
【经典LeetCode算法题目专栏分类】【第6期】二分查找系列:x的平方根、有效完全平方数、搜索二位矩阵、寻找旋转排序数组最小值