算法日记---二分查找

前言

一、二分查找

1.思想

2.简单二分

3.优点

4.局限性

二、模板

1.基本模板

2.简单例题（LeetCode）

4.有重复元素的二分

5.0-1问题

总结

前言

本文通过讲解简单的二分查找配合leetcode例题对二分查找本质、模板进行了基础的总结

提示：以下是本篇文章正文内容，下面案例可供参考

一、二分查找

1.思想

二分查找本质是折半查找思想，每一轮查找的范围是上一轮的一半，每次查找比较中间元素的值和目标值的大小。比较结论决定去哪一边作为下一轮的查找范围，循环直到查找范围为空。

2.简单二分

简单二分指的是数组不包含重复的元素，重点关注每次判边的逻辑。

3.优点

速度快 O(logn)且不需要额外的空间

4.局限性

有序：需要保证每次折半都有意义
数组：数组寻址的复杂度是 O (1)。如果是用链表存储一串数，二分查找是无意义的。链表的寻址是 O (n)。

二、模板

1.基本模板

二分查找的模板很多样，开闭的条件不同，判断的条件也不同

最本质的问题是当前判断结束后，下一次要取左半边还是右半边，缩小区间的条件是什么？判断的条件是什么

注意：

left<=right:实际进入循环时，left和right只向的元素不会进行if条件判断。比如left=right时，加此等号，才会对二者所指元素进行判断。否则不会。
mid =（left+right）>>>1：因为java会把最高位看成符号位，如果两个数过大，可能会导致数据溢出问题。我们需要通过无符号右移运算符来避免这种问题。还有一种写法是mid=left+(right-left)/2
更新left和right，避免死循环

public static int binarySerach(int[] a,int target){int left=0;int right=a.length-1;while(left<=right){int mid=(left+right)>>>1;if(target<a[mid]){//目标数在左边right=mid-1;}else if(a[mid]<target){//目标书在右边left=mid+1;}else{return mid;}}return -1;
}

2.简单例题（LeetCode）

1.704. 二分查找(基本简单)

class Solution {public int search(int[] nums, int target) {int left=0;int right=nums.length-1;while(left<=right){int mid=(left+right)>>>1;if(nums[mid]<target){left=mid+1;}else if(nums[mid]>target){right=mid-1;}else{return mid;}}return -1;}
}

2.744.寻找比目标字母大的最小字母

class Solution {public char nextGreatestLetter(char[] letters, char target) {int left=0;int right=letters.length-1;while(left<=right){int mid=(left+right)>>>1;if(letters[mid]<=target){left=mid+1;}else{right=mid-1;}}return left<letters.length?letters[left]:letters[0];}
}

3.74. 搜索二维矩阵

class Solution {public boolean searchMatrix(int[][] matrix, int target) {int left=0;//使用m*n将二维转为一维int m=matrix[0].length;int n=matrix.length;int right=m*n-1;while(left<=right){int mid=(left+right)>>>1;int x=matrix[mid/m][mid%m];//把mid元素转换回原二维矩阵的位置if(x==target){return true;}else if(x>target){right=mid-1;}else{left=mid+1;}}return false;}
}

4.162. 寻找峰值

此题究其本质依然是二分查找，我们需要根据题目重要条件进行理解

“你可以假设 nums[-1] = nums[n] = -∞ 。”

以下做法需要注意边界情况的判断

class Solution {public int findPeakElement(int[] nums) {int n = nums.length;if (n == 1) {return 0;}int left = 0, right = n - 1;while (left <= right) {int mid = left + (right - left) / 2;// 边界情况判断：数组第一个元素是峰值（只有它自己，或者比下一个大）if (mid == 0) {if (nums[mid] > nums[mid + 1]) {return mid;}}// 边界情况判断：数组最后一个元素是峰值（只有它自己，或者比前一个大）else if (mid == n - 1) {if (nums[mid] > nums[mid - 1]) {return mid;}}// 中间位置是峰值（比左右都大）else if (nums[mid] > nums[mid - 1] && nums[mid] > nums[mid + 1]) {return mid;}// 判断峰值在左侧还是右侧if (nums[mid] < nums[mid + 1]) {// 右侧有上升趋势，峰值在右侧left = mid + 1;} else if (nums[mid] < nums[mid - 1]) {// 左侧有上升趋势，峰值在左侧right = mid - 1;}}// 理论上不会走到这里，因为题目保证有解return -1;
}}

题解中的做法是无需单独判断边界情况的，也没有主动对mid元素与左右两元素进行比较

因为左右边界都是负无穷，找到往递增的一边方向找就一定能找到峰值（图中白圈内区域）。这就代表着 只要数组中存在一个元素比相邻元素大，那么沿着它一定可以找到一个峰值。

特点：一分为二后，一侧是有序数组，另一侧是循环数组。

根据这个特点，先判断有序数组、循环数组分别在哪一侧，再判断 target 在有序数组还是循环数组中

判断方法是让 target 和有序数组的首尾做比较，看是否在有序数组中。

1. 3. 搜索旋转排序数组

class Solution {public int search(int[] nums, int target) {int left=0;int right=nums.length-1;while(left<=right){int mid=(left+right)>>>1;if(nums[mid]==target){return mid;}//左半部分有序if(nums[left]<=nums[mid]){//目标值在左半部分区间内if(nums[left]<=target && target<nums[mid]){right=mid-1;}else{left=mid+1;//缩小范围到右半部分区间}}// 右半部分是有序的else {// 目标值在右半部分有序区间内if (nums[mid] < target && target <= nums[right]) {left = mid + 1;} else {right = mid - 1;//缩小范围到左半部分区间}}}return -1;}}

2.153. 寻找旋转排序数组中的最小值

不多说了，都在注解里：

最主要的还是需要判断目标值到底是在mid的左边还是右边，才能进行下一步二分。而判断依据就是根据两端递增区间的特性将nums[mid]和nums[right]进行比较。这也就是开篇说的判断取左半段还是右半段最重要的条件。

class Solution {public int findMin(int[] nums) {int left=0;int right=nums.length-1;while(left<=right){int mid=(left+right)>>>1;//首先由题可知，数组一定被分为了左右两个递增区间（或者没分，也就是0次旋转），且第一段所有元素大于第二段所有元素//需要比较nums[mid]和nums[right]的关系。//如果<=，意味着nums[mid]一定处于第二个递增区间，最小值要么是该元素，要么就在该元素左侧//如果>，意味着nums[mid]处于第一个递增区间。最小值一定在该元素右侧if(nums[mid]>nums[right]){//mid处于左半段left=mid+1;}else{//mid处于右半段if(mid==0||nums[mid]<=nums[mid-1]){//mid就是最小值,注意mid=0时索引越界问题return nums[mid];}else{//mid处于右半段，但最小值在mid的左边right=mid-1;}}}return -1;}
}

4.有重复元素的二分

通常要求找出第一个目标元素或是最后一个目标元素

存在重复元素的二分查找，无非就是多加了一个判断，判断是否为第一个/最后一个。

以查询第一个目标元素为例，判断条件就是看mid-1是否等于target，如果不是，那么mid就是我要

找的数了。这依然是二分关键。

public class BinarySearch {public static int binarySearch(int[] nums, int target) {int left = 0;int right = nums.length - 1;while (left <= right) {int mid = left + (right - left) / 2;if (nums[mid] < target) {left = mid + 1;} else if (nums[mid] > target) {right = mid - 1;} else {// 当找到目标值时，判断是否是第一个出现的位置if (mid == 0 || nums[mid - 1] != target) {//是第一个元素，注意索引越界问题。return mid;} else {right = mid - 1;}
//以下为找最后一个目标元素的判断条件
//if (mid == nums.length-1 || nums[mid+1]!=target){
//}else{
// left=mid+1;}}}return -1;}public static void main(String[] args) {int[] nums = {1, 3, 8, 8, 8, 9};int target = 8;int result = binarySearch(nums, target);System.out.println("第一个目标值 " + target + " 的索引是: " + result);}
}