关注并标星 3分钟秒懂大数据

每天1次，打卡阅读

获取AI大数据技术、面经、内推信息

Hello,各位小伙伴，我们都知道，在求职阶段，算法被作为大厂面试的一个核心考点，本阶段我将带领大家通过14天执行一个算法入门计划，具体内容如下：

算法入门：

第1天：二分查找

第2天：双指针

第3天：双指针

第4天：双指针

第5天：双指针

第6天：滑动窗口

第7天：广度优先搜索 / 深度优先有搜索

第8天：广度优先搜索 / 深度优先有搜索

第9天：广度优先搜索 / 深度优先有搜索

第10天：递归/回溯

第11天：递归/回溯

第12天：动态规划

第13天：位运算

第14天：位运算

通过上述14天训练，相信各位小伙伴们将对算法的分类有了一定的理解，同时，刷题能力也得到锻炼，好了，废话不多说，我们现在开始，let's go!

第1天：二分查找

二分查找思想：

二分查找是一种基于比较目标值和数组中间元素的教科书式算法。

如果目标值等于中间元素，则找到目标值。
如果目标值较小，继续在左侧搜索。
如果目标值较大，则继续在右侧搜索。

算法：

初始化指针 left = 0, right = n - 1。

当 left <= right：

比较中间元素 nums[pivot] 和目标值 target 。

如果 target = nums[pivot]，返回 pivot。

如果 target < nums[pivot]，则在左侧继续搜索 right = pivot - 1。

如果 target > nums[pivot]，则在右侧继续搜索 left = pivot + 1。

了解其基本思想和算法原理后，我们通过三道Leetcode题来加深巩固。

1、Leetcode 704 二分查找

1、题目介绍：

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

2、示例如下：

3、代码如下：

（1）JAVA版本

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

（2）Python版本

class Solution:    def search(self, nums: List[int], target: int) -> int:        left =0        right =len(nums)-1        while left<=right:            mid =(right+left)//2            if nums[mid] < target:                left = mid + 1            if nums[mid] > target:                right = mid - 1            if nums[mid] == target:                return mid        return -1

4、复杂度分析

2、Leetcode 278. 第一个错误的版本

1、题目介绍：

你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。

假设你有 n 个版本 [1, 2, ..., n]，你想找出导致之后所有版本出错的第一个错误的版本。

你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。

2、示例如下：

3、代码如下：

（1）JAVA版本

public class Solution extends VersionControl {    public int firstBadVersion(int n) {        int left = 1, right = n;        while (left < right) { // 循环直至区间左右端点相同            int mid = left + (right - left) / 2; // 防止计算时溢出            if (isBadVersion(mid)) {                right = mid; // 答案在区间 [left, mid] 中            } else {                left = mid + 1; // 答案在区间 [mid+1, right] 中            }        }        // 此时有 left == right，区间缩为一个点，即为答案        return left;    }}

（2）python版本

class Solution:    def firstBadVersion(self, n):        """        :type n: int        :rtype: int        """        left = 1        right = n        while left < right:            mid = left + (right-left)/2            if isBadVersion(mid):                right = mid            else:                left = mid+1        return right

4、复杂度分析

3、Leetcode 35. 搜索插入位置

1、题目介绍：

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

2、示例如下：

3、代码如下：

（1）JAVA版本

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

（2）python版本

class Solution(object):    def searchInsert(self, nums, target):        """        :type nums: List[int]        :type target: int        :rtype: int        """        left = 0        right = len(nums)-1        while left <=right:            mid = left +(right-left)/2            if nums[mid] ==target:                return mid            elif  nums[mid] < target:                left = mid +1            else:                right = mid - 1        return left

4、复杂度分析

以上就是14天算法入门-第1天-二分查找讲解内容！觉得好的，点赞，在看，分享三连击，谢谢！！！

End

最近整理了一份计算机类的书籍，包含python、java、大数据、人工智能、算法等，种类特别齐全。

获取方式：关注公众号：3分钟秒懂大数据，回复：福利，就可以获得这份超级大礼！，小伙伴们快来领取吧。

点个在看你最好看

ITPub博客

14天算法入门-第1天-二分查找

最新文章