（伪）二分
| 最近提交时间 | 题目 | 题目难度 | 提交次数 |
|---|---|---|---|
| 2 分钟前 | #4 寻找两个正序数组的中位数 | 困难 | 1 次 |
| 3 小时前 | #153 寻找旋转排序数组中的最小值 | 中等 | 1 次 |
| 4 小时前 | #33 搜索旋转排序数组 | 中等 | 3 次 |
| 4 小时前 | #34 在排序数组中查找元素的第一个和最后一个位置 | 中等 | 9 次 |
| 5 小时前 | #74 搜索二维矩阵 | 中等 | 1 次 |
| 5 小时前 | #35 搜索插入位置 | 简单 | 2 次 |
为什么叫（伪）二分？
是因为有些题目，直接蛮力法做，或者利用奇淫巧技更为简单。
备注：
1、搜索旋转数组 顺序区间判断 nums[l] <= nums[mid] 之后 if内判断 先 target >= nums[l] r = mid-1；
2、寻找排序数组最小值 while 判断 不需要等于， mid 的取值 l+(r-l)/2; if(nums[mid] < nums[r])
# 搜索插入位置
class Solution {
public int searchInsert(int[] nums, int target) {
if(nums == null){
return -1;
}
int l = 0;
int r= nums.length-1;
while(l <= r){
int mid = (l+r+1)/2;
if(nums[mid]>= target){
r = mid-1;
} else{
l = mid+1;
}
}
return l;
}
}
思路：
1、经典二分，要是不会做，直接回家种地！！！！
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 搜索二维矩阵
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
for(int[] item: matrix){
for(int i:item){
if(i == target){
return true;
}
}
}
return false;
}
}
思路：
1、此题直接蛮力法解决
1
2
3
4
5
6
7
8
9
10
11
12
13
14
2
3
4
5
6
7
8
9
10
11
12
13
14
# 在排序数组中查找第一个 跟最后一个 target 出现的位置
class Solution {
// 两次二分查找，分开查找第一个和最后一个
// 时间复杂度 O(log n), 空间复杂度 O(1)
// [1,2,3,3,3,3,4,5,9]
public int[] searchRange(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
int first = -1;
int last = -1;
// 找第一个等于target的位置
while (left <= right) {
int middle = (left + right) / 2;
if (nums[middle] == target) {
first = middle;
right = middle - 1; //重点
} else if (nums[middle] > target) {
right = middle - 1;
} else {
left = middle + 1;
}
}
// 最后一个等于target的位置
left = 0;
right = nums.length - 1;
while (left <= right) {
int middle = (left + right) / 2;
if (nums[middle] == target) {
last = middle;
left = middle + 1; //重点
} else if (nums[middle] > target) {
right = middle - 1;
} else {
left = middle + 1;
}
}
return new int[]{first, last};
}
}
思路：
1、经典二分 *2
2、就是分解为两个二分 分别寻找第一个位置跟最后一个位置
3、right = middle - 1; //重点
4、 left = middle + 1; //重点
5、都是在mid跟 target 相等的时候进行赋值的
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
# 搜索旋转排序数组
class Solution {
public int search(int[] nums, int target) {
int l = 0;
int r = nums.length-1;
while(l<=r){
int mid = l + (r-l)/2;
if(nums[mid] == target){
return mid;
}
// 顺序区间
if(nums[l] <= nums[mid]){
if(target >= nums[l] && target < nums[mid]){
r = mid-1;
} else {
l =mid+1;
}
} else {
if(target > nums[mid] && target <= nums[r]){
l =mid+1;
} else {
r = mid-1;
}
}
}
return -1;
}
}
思路：
1、经典二分
2、只要记住一点 二分的前提必须是在有序区间内
3、所以这里 mid对于 l跟 r 的赋值 判断了区间
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
# 寻找旋转数组的最小值
class Solution {
public int findMin(int[] nums) {
int l = 0;
int r = nums.length-1;
while(l < r){
int mid = l + (r-l)/2;
if(nums[mid] < nums[r]){
r = mid;
} else{
l++;
}
}
return nums[l];
}
}
思路：
1、经典二分
2、关键是 mid跟 r的比较，如果mid小 那么缩小r为mid 否则l++进行下一轮循环，最后l 就是要找的位置
3、如果这个道题换成找最大值，那么就是mid 跟l 比 最大了 r--循环了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 寻找两个正序数组的中位数
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
List<Integer> list = toList(nums1);
list.addAll(toList(nums2));
Collections.sort(list);
int index = list.size()/2;
if(list.size() % 2 == 0){
return (list.get(index-1) + list.get(index) )/2.0;
} else {
return list.get(index);
}
}
public List<Integer> toList(int[] nums){
List<Integer> res = new ArrayList<>();
for(int i:nums){
res.add(i);
}
return res;
}
}
思路：
1、两个数组统一放到list
2、对list排序
3、直接去list的中间位置
4、判断数量的奇偶
5、分别求取中位数返回
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
上次更新: 2024/03/26, 9:03:00