算法题——二分查找类型题大全
一、二分查找
题目链接：. - 力扣（LeetCode）. - 备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。
https://leetcode.cn/problems/binary-search/
解题思路：
从有序的数组中查找一个值可以是用二分查找的方法。
！！！求中间下标的时候不建议使用(right +left)/2，因为当数据过大的时候可能会造成溢出。
代码实现：
class Solution {public int search(int[] nums, int target) {int left = 0;int right = nums.length - 1;int mid ;while(left <=right){mid = left + (right - left) / 2;//使用这种方法计算中间点可以防溢出 if(nums[mid] == target){return mid;}else if(nums[mid] < target){left = mid + 1;}else{right = mid - 1;}}return -1;}
}二、在排序数组中查找元素的第一个和最后一个位置
题目链接：. - 力扣（LeetCode）. - 备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/description/
解题思路：
代码实现：
class Solution {public int[] searchRange(int[] nums, int target) {if (nums.length == 0) {return new int[] { -1, -1 };}int left = 0, right = nums.length - 1, mid = 0;int[] array = new int[2];// 二分查找查找左端点while (left < right) {mid = left + (right - left) / 2;if (nums[mid] < target) {left = mid + 1;} else {right = mid;}}// 确定数组是否含有target值以及左端点下标if (nums[right] == target) {array[0] = right;} else {// 说明数组中没有target值return new int[] { -1, -1 };}// 查找右端点left = 0;right = nums.length - 1;while (left < right) {mid = left + (right - left + 1) / 2;if (nums[mid] <= target) {left = mid;} else {right = mid - 1;}}// 将右端点加入数组array[1] = right;return array;}
}三、x的平方根
题目链接：. - 力扣（LeetCode）. - 备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/jJ0w9p/description/
解题思路：
代码实现：
class Solution {public int mySqrt(int x) {// 细节if (x < 1)return 0;long left = 1, right = x, mid = 0;// 找端点while (left < right) {mid = left + (right - left + 1) / 2;if (mid * mid <= x) {left = mid;} else {right = mid - 1;}}return (int) left;}
}四、搜索插入位置
题目链接：. - 力扣（LeetCode）. - 备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/N6YdxV/
解题思路：
代码实现：
class Solution {public int searchInsert(int[] nums, int target) {int left = 0,right = nums.length - 1,mid = 0;while(left < right){mid = left + (right - left) / 2;if(nums[mid]>=target){right = mid;}else{left = mid + 1;}}//如果数组中没有大于等于target的值,返回right + 1if(nums[right] < target){return right + 1;}return right;}
}五、山峰数组的峰顶索引
题目链接：. - 力扣（LeetCode）. - 备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/B1IidL/
解题思路：
代码实现：
class Solution {public int peakIndexInMountainArray(int[] arr) {//通过分析得到数组具有二段性，因此可以使用二分查找算法int left = 0,right = arr.length - 1,mid = 0;while(left < right){mid = left + (right - left + 1) / 2;if(arr[mid] > arr[mid - 1]){left = mid;}else{right = mid - 1;}}return right;}
}六、寻找峰值
题目链接：. - 力扣（LeetCode）. - 备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/find-peak-element/
解题思路：
代码实现：
1.解法一代码：
class Solution {public int findPeakElement(int[] nums) {int left = 0,right = nums.length - 1,mid = 0;while(left < right){mid = left + (right - left + 1) / 2;if(nums[mid] > nums[mid -1]){left = mid;}else{right = mid - 1;}}return left;}
}2.解法二代码：
class Solution {public int findPeakElement(int[] nums) {int left = 0,right = nums.length - 1,mid = 0;while(left < right){mid = left + (right - left) / 2;if(nums[mid] > nums[mid + 1]){right = mid;}else{left = mid + 1;}}return left;}
}七、寻找旋转排序数组中的最小值
题目链接：. - 力扣（LeetCode）. - 备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array/
解题思路：
思考：是否可以选择nums[0]来确定nums[mid]属于哪个区域？
代码实现：
class Solution {public int findMin(int[] nums) {int left = 0,right = nums.length - 1,mid = 0;while(left < right){mid = left + (right - left) / 2;if(nums[mid] > nums[nums.length - 1]){left = mid + 1;}else{right = mid;}}return nums[left];}
}