算法题——二分查找类型题大全

一、二分查找

题目链接：. - 力扣（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];}
} 

---