数据结构与算法-二分查找
二分查找的分类
- 基本的二分查找
- 等于给定值的第一个元素和最后一个元素
- 旋转排序数组的二分查找
- 小于等于给定值的第一个元素
- 大于等于给定值的第一个元素
基本的二分查找
704. 二分查找
1
2
3
4
5
6
7
8
9
10
11
12
13
14
func search(nums []int, target int) int {
left, right := 0, len(nums) - 1
for left <= right {
mid := left +(right - left)/2
if nums[mid] == target {
return mid
} else if nums[mid] > target {
right = mid - 1
} else {
left = mid + 1
}
}
return -1
}
等于给定值的第一个元素和最后一个元素
34. 在排序数组中查找元素的第一个和最后一个位置
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
class Solution {
public int[] searchRange(int[] nums, int target) {
int left = searchLeft(nums, target);
int right = searchRight(nums, target);
return new int[]{left, right};
}
public int searchLeft(int[] nums, int target) {
int left = 0, right = nums.length - 1;
int first = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] > target) {
right = mid - 1;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
first = mid;
right = mid - 1;
}
}
return first;
}
public int searchRight(int[] nums, int target) {
int left = 0, right = nums.length - 1;
int last = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] > target) {
right = mid - 1;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
last = mid;
left = mid + 1;
}
}
return last;
}
}
剑指 Offer 53 - I. 在排序数组中查找数字 I
1
write your code here
旋转排序数组的二分查找
33. 搜索旋转排序数组
1
write your code here
81. 搜索旋转排序数组 II
注意：数组可能包含重复元素
1
write your code here
面试题 10.03. 搜索旋转数组
1
write your code here
153. 寻找旋转排序数组中的最小值
1
write your code here
154. 寻找旋转排序数组中的最小值 II
注意：数组可能包含重复元素
1
write your code here
剑指 Offer 11. 旋转数组的最小数字
注意：本题与主站 154 题相同
二分查找经典题目
1
write your code here
百度面试题-有序数组中绝对值最小的元素
1
write your code here
540. 有序数组中的单一元素
1
write your code here
278. 第一个错误的版本
1
write your code here
744. 寻找比目标字母大的最小字母
1
write your code here
162. 寻找峰值
1
write your code here
852. 山脉数组的峰顶索引
1
write your code here
本博客所有文章除特别声明外，均采用
CC BY-NC-SA 4.0
许可协议，转载请注明出处！