大厂高级程序员必备算法，看似简单的二分查找，您了解多少？ _算法

一、基础概念1、Sorted（单调递增or单调递减）
2、Bounded(存在上下界)
3、Accessible by index（能够通过索引访问，数组适合，but链表不适合）
二分查找是一种在每次比较之后将查找空间一分为二的算法。每次需要查找集合中的索引或元素时，都应该考虑二分查找。如果集合是无序的，我们可以总是在应用二分查找之前先对其进行排序。
二分查找一般由三个主要部分组成：
1、预处理--如果有集合未排序，则进行排序。
2、二分查找--使用循环或递归在每次比较后将查找空间划分为两半
3、后处理--在剩余空间中确定可行的候选者
例如：给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1 。
示例 1:
输入: nums = [-1,0,3,5,9,12], target = 9输出: 4解释: 9 出现在 nums 中并且下标为 4示例 2:
输入: nums = [-1,0,3,5,9,12], target = 2输出: -1解释: 2 不存在 nums 中因此返回 -1提示：
1、你可以假设 nums 中的所有元素是不重复的。
2、n 将在 [1, 10000]之间。
3、nums 的每个元素都将在 [-9999, 9999]之间。

step01: 设定初始值 left和 right：

文章插图

step02: 设定中间指针 mid = left + (right-left)/2：

文章插图

step03：

文章插图

step04：

文章插图

step05：

文章插图

step06：

文章插图

step07：

文章插图

二、通用模版2.1 模版一

var binarySeach(nums,target){if(nums == null|| nums.length ==0){return -1;}let left =0,right=nums.length- 1; //初始条件while(left<=right){ //终止条件 left>rightlet mid = Math.floor(left + (right-left)/2);if(nums[mid] == target){return mid;} else if(nums[mid]<target){left = mid + 1; //向右查找}else{right = mid - 1; //向左查找}}return -1;}

关键属性：

二分查找的最基础和最基本的形式
查找条件可以在不与元素的两侧进行比较的情况下确定（或使用它周围的特定元素）
不需要后处理，因为每一步中，你都在检查是否找到了元素。如果到达末尾，则指导未找到该元素。

2.2 模版二

var binarySeach(nums,target){if(nums == null|| nums.length ==0){return -1;}let left =0,right=nums.length; //初始条件while(left<right){ //终止条件 left>=rightlet mid = Math.floor(left + (right-left)/2);//阻止(left+right)溢出if(nums[mid] == target){return mid;} else if(nums[mid]<target){left = mid + 1; //向右查找}else{right = mid; //向左查找}}if(left !=nums.length && nums[left] == target) return left;return -1;}

模版二：是二分查找的高级模板。它用于查找需要访问数组中当前索引及其直接右邻居索引的元素或条件。
关键属性：

一种实现二分查找的高级方法
查找条件需要访问元素的直接右邻居
使用元素的右邻居来确定是否满足条件，并决定是向左还是向右
保证查找空间在每一步中至少有2个元素
需要进行后处理，当你剩下一个元素的时候，循环/递归结束。需要评估剩余元素是否符合条件

2.3 模版三

var binarySeach(nums,target){if(nums == null|| nums.length ==0){return -1;}let left =0,right=nums.length-1; //初始条件while(left+1 < right){ //终止条件 left+1 == rightlet mid = Math.floor(left + (right-left)/2);//阻止(left+right)溢出if(nums[mid] == target){return mid;} else if(nums[mid]<target){left = mid; //向右查找}else{right = mid; //向左查找}}if(nums[left] == target) return left;if(nums[right] == target) return right;return -1;}

模版3是二分法查找的另一种独特形式。它用于搜索需要访问当前索引及其在数组中的直接左右邻居索引的元素或条件。
关键属性：