14天算法入门-第1天-二分查找
关注并标星 3分钟秒懂大数据
每天1次，打卡阅读
获取AI大数据技术、面经、内推信息
Hello,各位小伙伴，我们都知道，在求职阶段，算法被作为大厂面试的一个核心考点，本阶段我将带领大家通过14天执行一个算法入门计划，具体内容如下：
算法入门：
第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 =0right =len(nums)-1while left<=right:mid =(right+left)//2if nums[mid] < target:left = mid + 1if nums[mid] > target:right = mid - 1if nums[mid] == target:return midreturn -1
2、Leetcode 278. 第一个错误的版本
1、题目介绍：
你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。
假设你有 n 个版本 [1, 2, ..., n]，你想找出导致之后所有版本出错的第一个错误的版本。
你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。
2、示例如下：
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;}}
class Solution:def firstBadVersion(self, n):""":type n: int:rtype: int"""left = 1right = nwhile left < right:mid = left + (right-left)/2if isBadVersion(mid):right = midelse:left = mid+1return right
3、Leetcode 35. 搜索插入位置
1、题目介绍：
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
2、示例如下：
3、代码如下：
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;}}
class Solution(object):def searchInsert(self, nums, target):""":type nums: List[int]:type target: int:rtype: int"""left = 0right = len(nums)-1while left <=right:mid = left +(right-left)/2if nums[mid] ==target:return midelif nums[mid] < target:left = mid +1else:right = mid - 1return left
End
最近整理了一份计算机类的书籍，包含python、java、大数据、人工智能、算法等，种类特别齐全。
3分钟秒懂大数据
专注于大数据、机器学习、深度学习等技术博文的分享，提供最前沿的技术博客!
Official Account
点个在看你最好看