因此可以使用二分查找算法

🌸个人主页:https://blog.csdn.net/2301_80050796?spm=1000.2115.3001.5343
🏵️热门专栏:
🧊 Java基本语法(97平均质量分)https://blog.csdn.net/2301_80050796/category_12615970.html?spm=1001.2014.3001.5482
🍕 Collection与数据结构 (92平均质量分)https://blog.csdn.net/2301_80050796/category_12621348.html?spm=1001.2014.3001.5482
🧀Java EE(96平均质量分) https://blog.csdn.net/2301_80050796/category_12643370.html?spm=1001.2014.3001.5482
🍭MySql数据库(93平均质量分)https://blog.csdn.net/2301_80050796/category_12629890.html?spm=1001.2014.3001.5482
🍬算法(97平均质量分)https://blog.csdn.net/2301_80050796/category_12676091.html?spm=1001.2014.3001.5482
🍃 Spring(97平均质量分)https://blog.csdn.net/2301_80050796/category_12724152.html?spm=1001.2014.3001.5482
感谢点赞与关注~~~

1. 二分查找(难度:🟢1度)

OJ链接

• 题目描述

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
请必须使用时间复杂度为 O(log n) 的算法。说明[mid + 1, right] （因为mid 可能是最终结果，不能舍去）是可以舍去的，此时更新right 到mid 的位置，由于mid的位置可能是最终的值,所以mid位置不可以舍去,不需要-1继续在[left, mid] 上寻找左边界；
• 由此，就可以通过⼆分，来快速寻找左边界；
[注意] 循环条件判断必须是left < right,如果加上等号,当找到目标值的时候.left和right重合,第一重合就证明已经找到了目标值,就没有必要再执行操作了,第二,如果找到了目标值,left和right依然会满足条件,会进入循环,会让程序陷入死循环.求中点的时候,必须采用向下取整的方式,如果采用向上取整,如果找到了目标值,right=mid的时候,right没有移动,就会陷入死循环.

寻找右边界
与寻找左边界同理
◦ 用resRight 表示右边界；
◦ 我们注意到右边界的特点：
▪ 左边区间（包括右边界） [left, resRight] 都是小于等于x 的；
▪ 右边区间[resRight+ 1, right] 都是大于x 的；
• 因此，关于mid 的落点，我们可以分为下面两种情况：
◦ 当我们的mid 落在[left, resRight] 区间的时候，说明[left, mid - 1]（ mid 不可以舍去，因为有可能是最终结果）都是可以舍去的，此时更新left 到mid 的位置；
◦ 当mid 落在[resRight+ 1, right] 的区间的时候，说明[mid, right] 内的元素是可以舍去的，此时更新right 到mid - 1 的位置；
• 由此，就可以通过⼆分，来快速寻找右边界；

代码实现

classSolution{publicint[]searchRange(int[]nums,inttarget){intleft =0;intright =nums.length -1;int[]array =newint[2];array[0]=-1;array[1]=-1;if(nums.length ==0){//注意处理特殊情况returnarray;}while(left <right){intmid =left +(right -left)/2;if(nums[mid]<target){left =mid +1;//left下标不可能是t的值}else{right =mid;//right下标有可能是t的值}}if(nums[left]==target){array[0]=left;}else{returnarray;}left =0;right =nums.length -1;while(left <right){intmid =left +(right -left +1)/2;if(nums[mid]>target){right =mid -1;//right下标不可能是t的值}else{left =mid;//left下标可能是t的值}}array[1]=right;returnarray;}}

• 查找边界二分算法模版
  • 左边界

  while(left < right){	int mid = left+(right-left)/2;	if(...) left = mid+1;	else right = mid;}

  • 右边界

  while(left < right){int mid = left+(right-left+1)/2;if(...) left = mid;else right = mid-1;}

3. 搜索插入位置(难度:🔵2度)

OJ链接

• 题目解析

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。
b. 找到待查找区间的中间点mid,找到之后分三种情况讨论：
i. arr[mid] == target 说明正好找到，返回mid 的值；
ii. arr[mid] > target 说明[mid, right] 这段区间都是大于target 的，因此舍去右边区间，在左边[left, mid -1] 的区间继续查找，即让right = mid - 1 ，然后重复2 过程；
iii. arr[mid] < target 说明[left, mid] 这段区间的值都是小于target 的，因此舍去左边区间，在右边[mid + 1, right] 区间继续查找，即让left = mid + 1，然后重复2 过程；
c. 当left 与right 错开时，说明整个区间都没有这个数，返回-1

代码实现

classSolution{publicintsearch(int[]nums,inttarget){intleft =0,right =nums.length-1;while(left <=right){intmid =left +(right-left)/2;if(target <nums[mid]){right =mid -1;}elseif(target >nums[mid]){left =mid +1;}else{returnmid;}}return-1;}}

[注意事项]

1. 计算mid的时候,没有使用(left+right)/2,而是使用left+(right-left)/2的形式.
2. 二分法一般采用最中间的点作为划分点,其他的等分点也可以作为划分点,但是查找效率没有中间作为划分点高.

• 朴素二分模版总结

//首先定义left和right指针while (left <= right){	int mid = left+(right-left)/2;	if(...) left = mid+1;	else if(...) right = mid-1;	else return ...;}

2. 在排序数组中查找元素的第一个和最后一个位置(难度:🟡3度)

OJ链接

• 题目描述

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。