二分查找一般操作的是有序的数组
# 一、简介
二分查找一般操作的是有序的数组
# 二、手写
二分查找有序数组且不重复
const binarySearch = (arr, target) => {
let len = arr.length
if (len === 0) return -1
let low = 0
let hight = len - 1
while (low <= hight) {
const mid = Math.floor((low + hight) / 2)
if (target === arr[mid]) {
return mid
} else if (target < arr[mid]) {
hight = mid - 1
} else {
low = mid + 1
}
}
return -1
}
const arr = [1, 4, 5, 6, 7, 8, 10, 11, 23, 42, 44, 54, 56, 77, 102]
console.log(binarySearch(arr, 44))
console.log(binarySearch(arr, 1))
console.log(binarySearch(arr, 102))
console.log(binarySearch(arr, 1111))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 三、思考题
# 1. 查找第一个值等于给定值的元素
// （1）查找第一个值等给定值的元素
// 在循环中，如果我们找到的等于给定值的值，而且这个值「位于整个数组的第一个位置或者它前面那个元素小于给定值」,前面的数字可能相同
const first = (arr, target) => {
let len = arr.length
if (len === 0) return -1
let low = 0
let hight = len - 1
while (low <= hight) {
let mid = Math.floor((hight + low) / 2)
if (target > arr[mid]) {
low = mid + 1
} else if (target < arr[mid]) {
hight = mid - 1
} else {
if (mid === 0 || arr[mid - 1] !== target) {
return mid
} else {
hight = mid - 1
}
}
}
return -1
}
const arr1 = [1, 2, 3, 4, 4, 4, 4, 4, 6, 7, 8, 8, 9]
const data1 = first(arr1, 4)
console.log(data1)
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
# 2. 查找最后一个值等于给定值的元素
// 查找最后一个相等的数
const last = (arr, target) => {
let len = arr.length
if (len === 0) return -1
let low = 0
let hight = len - 1
while (low <= hight) {
let mid = Math.floor((hight + low) / 2)
if (target > arr[mid]) {
low = mid + 1
} else if (target < arr[mid]) {
hight = mid - 1
} else {
if (mid === 0 || arr[mid + 1] !== target) {
return mid
} else {
low = mid + 1
}
}
}
return -1
}
const arr1 = [1, 2, 3, 4, 4, 4, 4, 4, 6, 7, 8, 8, 9]
const data2 = last(arr1, 4)
console.log(data2)
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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# 3. 查找第一个大于等于给定值的元素
// 查找第一个大于等于给定值的元素
const firstBig = (arr, target) => {
let len = arr.length
if (len === 0) return -1
let low = 0
let hight = len - 1
while (low <= hight) {
let mid = Math.floor((hight + low) / 2)
if (target > arr[mid]) {
low = mid + 1
} else {
if (mid === 0 || arr[mid + 1] !== target) {
return mid
} else {
if (mid === 0 || arr[mid - 1] < target) {
return mid
} else {
hight = mid - 1
}
}
}
}
return -1
}
const arr1 = [1, 2, 3, 4, 4, 4, 4, 4, 6, 7, 8, 8, 9]
const data3 = firstBig(arr1, 5)
console.log(data3)
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
# 4. 查找第一个小于等于给定值的元素
// 查找最后一个小于等于给定值的元素
const lastSmall = (arr, target) => {
let len = arr.length
if (len === 0) return -1
let low = 0
let hight = len - 1
while (low <= hight) {
let mid = Math.floor((hight + low) / 2)
if (target < arr[mid]) {
hight = mid - 1
} else {
if (mid === 0 || arr[mid + 1] >= target) {
return mid
} else {
low = mid + 1
}
}
}
return -1
}
const arr1 = [1, 2, 3, 4, 4, 4, 4, 4, 6, 7, 8, 8, 9]
const data4 = lastSmall(arr1, 4)
console.log(data4)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# 5. x的平方根（#69）
实现 int sqrt(int x) 函数。
计算并返回 x 的平方根， 其中 x 是非负整数。
由于返回类型是整数， 结果只保留整数的部分， 小数部分将被舍去。
示例 1:
输入: 4
输出: 2
示例 2:
输入: 8
输出: 2
说明: 8 的平方根是 2.82842...,
由于返回类型是整数， 小数部分将被舍去。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
解法一： 利用二分查找，中间值变成mid*mid
var mySqrt = function(x) {
let left = 0;
let right = x;
let mid;
if (x < 2) return x;
while (left <= right) {
mid = Math.floor((left + right) / 2);
const temp = mid * mid;
if (temp === x || mid === left) return mid;
if (temp > x) right = mid;
else left = mid;
}
return mid || 0;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
116 ms 36. 2 MB
解法二： 利用数组方法
var mySqrt = function(x) {
return parseInt(Math.sqrt(x));
};
1
2
3
2
3
84 ms 35. 9 MB
# 6. 如何快速定位出一个ID地址的归属地
- 如果 IP 区间与归属地的对应关系不经常更新，我们可以先预处理这 12 万条数据，让其按照起始IP 从小到大排序。
- IP 地址可以转化为 32 位的整型数。所以，我们可以将起始地址，按照对应的整型值的大小关系，从小到大进行排序。
- 对应第四种变形问题“在有序数组中，查找最后一个小于等于某个给定值的元素”了。
当我们要查询某个 IP 归属地时，我们可以先通过二分查找，找到最后一个起始 IP 小于等于这个 IP 的 IP 区间，然后，检查这个 IP 是否在这个 IP 区间内，如果在，我们就取出对应的归属地显示；如果不在，就返回未查找到。 （待续）
# 7. 搜索旋转排序数组（数组有两段，分别是有序的）（#33）
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
(例如， 数组[0, 1, 2, 4, 5, 6, 7] 可能变为[4, 5, 6, 7, 0, 1, 2])。
搜索一个给定的目标值， 如果数组中存在这个目标值， 则返回它的索引， 否则返回 - 1。
你可以假设数组中不存在重复的元素。
你的算法时间复杂度必须是 O(log n) 级别。
示例 1:
输入: nums = [4, 5, 6, 7, 0, 1, 2], target = 0
输出: 4
示例 2:
输入: nums = [4, 5, 6, 7, 0, 1, 2], target = 3
输出: -1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
（待续）
# 8. 如何在 1000 万个整数中快速查找某个整数？（快速排序 ，小顶堆）
（待续）