前言今日练习目的掌握二分查找标准解体模板左闭右开写法二分查找类题目的特点是查找区间内有序且有明确的上下界704二分查找题目要求给定一个升序排列的整数数组nums和整数target要求写一个函数如果target在数组中存在返回它的下标否则返回-1.核心思路左闭右开区间包括[left] 不包括right循环条件while(leftright)更新边界代码实现intleft0;intrightnums.length;while(leftright){intmidleft(right-left)/2;if(nums[mid]target){returnmid;}elseif(nums[mid]target){leftmid1;}else{rightmid-1;}retunr-1;总结对于左闭右开的做法有几注意点while中 leftrightrigthnums.lengthrightmid35搜索插入位置题目要求给定一个升序排列的数组 nums 和一个 目标值 target请你返回 目标值在数组中的索引如果数组中不存在目标值则返回 目标值应该被插入的位置。核心思路用二分查找确定目标值的位置或插入位置使用左闭右开比较nums[mid]与target循环结束代码实现intleft0;intrightnums.length;while(leftright){intmidleft(right-left)/2;if(nums[mid]target){leftmid1;}else{rightmid;}}return-1;总结上一题的变种返回值类型不一样。本题返回目标值下标索引。34在排序数组中查找元素的第一个和最后一个位置题目要求给定一个神仙古列表的整数数组nums和整数target要求长出target在整数组中的起始和结束位置。核心思路拆成两个二分查找找出第一个target的下标起始位置找到第二个target的下标结束位置代码实现classSolution{publicint[]searchRange(int[]nums,inttarget){int[]res{-1,-1};if(numsnull||nums.length0)returnres;//找第一个target的下标intstartfindFirstGreaterEqual(nums,target);//找第二个target的下标intendfindFirstGreaterEqual(nums,target1)-1;if(startnums.lengthnums[start]target){res[0]start;res[1]end;}returnres;}//左闭右开二分查找返回第一个target的下标privateintfindFirstGreaterEqual(int[]nums,inttarget){intleft0,rightnums.length;while(leftright){intmidleft(right-left)/2;if(nums[mid]target){leftmid1;}else{rightmid;}}returnleft;}}总结因为本题需要用到两次二分查找方法所以我们通过自己构造二分查找的方法来达到实现目标。掌握两次使用二分查找的思路注意找到start与end的实现方法33搜索旋转排序数组题目要求给定一个升序列表的整数数组nums数组在某个未知索引进行了旋转给定一个target要求如果数组中存在这个元素返回他们的下标否则返回-1核心思路本题是旋转数组二分查找关键在于多了一步target在哪边使用左闭右开区间判断mid所在的区间是否有序根据target的位置调整左右指针左半段有序如果target在nums[left],nums[mid]代码实现intleft0,rightnums.length;while(leftright){intmidleft(rigth-left)/2;if(nums[mid]target)returnmid//左半段有序if(nums[left]nums[mid]){if(nums[lefttargettargetnums[mid]){rightmid;}else{leftmid1;}//右半段有序else{if(nums[mid]targettargetnums[right]){leftmid1;}else{leftmid1;}}}return-1;总结本题多了一个变量因素就是将数组翻转导致数组不是递增的。为了找到target只能在有序数组中二分查找所以我们会先将有序的部分筛选出来左半段与右半段有序的判断二分查找的核心要求是针对有序区间接着判断target是否在有序数组中进一步缩小target的位置