算法: 二分查找题目练习

---

二分查找

二分查找

没啥可说的,轻轻松松~

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

在排序数组中查找元素的第一个和最后一个位置

可以使用二分查找.

查找左端点:

• 把区间划分成两个部分, 1. num[mid] < t , num[mid] >= t .
  把区间划分成 num[mid] < t 和 num[mid] > t ,这谁都懂,就不说了.
  关键是 “=” 给谁? 左边还是右边?
  关于为啥给右边,这里就不说了.
  我在这里只是讲一个记忆方法(左右都适用):
  求左端点,只看左括号,哪个括号在中间,“=” 就给谁.
  具体如下:
• 划分好区间,接下来就要想指针的移动方式了.
  

查找右端点:

• 把区间划分成两个部分, 1. num[mid] <= t , num[mid] > t .
  “=” 给谁,参考上面的记忆方法.

  • 求右端点,只看右括号,哪个括号在中间,“=” 就给谁.

• 指针的移动方式,跟查找左端点的方法类似,自己写写试试~

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

坑:

• nums 数组的长度可能为0.
• 二分没写好,容易死循环.

我在写完以后,有个疑问:

• 为啥循环结束后 mid 指向的值,不是我们想要的?

确实困惑了我一会,不过后来一想就明白了,因为出循环后 mid 差一次更新 ( left 或 right已经变了,但是 mid 没有变).

搜索插入位置

用查找左端点的方法,秒了~

坑:

• 注意边界情况 nums[nums.length-1] < target.

class Solution {public int searchInsert(int[] nums, int target) {if(nums[nums.length-1] < target) return nums.length;int left=0,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;}}return right;}
}

用左端点做完以后,我想了想,为啥不能用右端点做呢?
确实困扰了我一会,后来明白了,题目要查找的值是要 >= target 的.
而使用查找右端点的方法,会漏掉 > target 的情况:

x 的平方根

分析一下,可以把区间划分成 mid*mid <= x 和 mid*mid > x.一看就是右端点,秒了~

坑:

• 数值过大,要用 long 类型.

class Solution {public int mySqrt(int x) {long left = 0, right = x;while (left < right) {long mid = left + (right - left + 1) / 2;if (mid * mid <= x) {left = mid;} else {right = mid - 1;}}return (int) left;}
}

山脉数组的峰顶索引

没想到怎么把数组划分成两部分.
也就是 if(...) 中的条件不会写.

看了看题解,没想到还能这样做.
以 arr[mid - 1] < arr[mid] 划分~

class Solution {public int peakIndexInMountainArray(int[] arr) {int left = 0, right = arr.length - 1;while (left < right) {int mid = left + (right - left + 1) / 2;if (arr[mid - 1] < arr[mid]) {left = mid;} else {// 前面括号内有 +1 ,这里就 -1 .right = mid - 1;}}return left;}
}

寻找峰值

画图不能偷懒,要老老实实的画,写全了~

	public int findPeakElement(int[] nums) {int left = 0;int right = nums.length - 1;while (left < right) {int mid = left + (right - left) / 2;if (nums[mid] < nums[mid + 1]) {left = mid + 1;} else {right = mid;}}return left;}

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

没想出来,题解是用 n-1 这个位置的数来划分区间的.

	public int findMin(int[] nums) {int left = 0;int right = nums.length - 1;while (left < right) {int mid = left + (right - left) / 2;if (nums[mid] < nums[nums.length - 1]) {right = mid;} else {left = mid + 1;}}return nums[right];}

下面这个是用 0 位置来划分区间的(需要考虑一个特殊情况~).

	public int findMin(int[] nums) {int left = 0;int right = nums.length - 1;if (nums[0] < nums[nums.length - 1]) {return nums[0];}while (left < right) {int mid = left + (right - left) / 2;if (nums[mid] < nums[0]) {right = mid;} else {left = mid + 1;}}return nums[right];}

点名

写出来了,用的二分~

class Solution {public int takeAttendance(int[] records) {int left = 0;int right = records.length-1;while(left < right) {int mid = left + (right-left+1)/2;if(records[mid] > mid) {right = mid -1;}else if(records[mid] == mid){left = mid;}}return right==records[right]?right+1:right;}
}

总结

• 当有 二段性 时,就可以用二分查找,不必有序~

  二段性: 通过某个条件,可以把数组分成两部分,根据题意可以舍弃一部分,这就叫二段性.

精华

查找左端点:

• 求左端点,只看左括号,哪个括号在中间,“=” 就给谁.
  具体如下:
• 划分好区间,接下来就要想指针的移动方式了.
  

查找右端点同理.

模版

---

本文到这里就结束啦~