算法: 二分查找题目练习

文章目录

二分查找
- 二分查找
- 在排序数组中查找元素的第一个和最后一个位置
- 搜索插入位置
- x 的平方根
- 山脉数组的峰顶索引
- 寻找峰值
- 寻找旋转排序数组中的最小值
- 点名
总结
- 精华
- 模版

二分查找

在这里插入图片描述
没啥可说的,轻轻松松~

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;}
}