概述
讨论一下关于数组的简单算法
二分查找
二分查找主要点在于边界条件判断，即结束 while 循环的时机。
当判断左边界大于右边界时，即可确定数组内没有要查找的元素，即可跳出循环体。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
search(nums, target) {
let left = 0,
right = nums.length - 1;
while (left <= right) {
let middle = Math.floor((left + right) / 2);
if (nums[middle] > target) {
right = middle - 1;
} else if (nums[middle] < target) {
left = middle + 1;
} else {
return middle;
}
}
return -1;
}
|
算法地址
查找索引
题目描述：
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]
算法地址
该问题可以直接简单粗暴的循环两遍，得到左索引和右索引，时间复杂度为 O(n)；但是题目明显是需要更快的时间复杂度，而涉及到排序好的数组操作，优先考虑二分法，用来达到 O(logn)的时间复杂度。
二分法查找开始位置和结束位置，首先查找开始位置，用条件不断逼近左值，得到左值后在其基础上逼近右值（需要重新设置右值为数组最大长度）。
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
| searchRange(nums, target) {
let left = 0,
right = nums.length - 1,
res = [-1, -1];
while (left < right) {
let mid = Math.floor((left + right) / 2);
if (nums[mid] >= target) {
right = mid;
} else {
left = mid + 1;
}
}
if (nums[left] !== target) {
return res;
} else {
res[0] = left;
}
right = nums.length;
while (left < right) {
let mid = Math.floor((left + right) / 2);
if (nums[mid] <= target) {
left = mid + 1;
} else {
right = mid;
}
}
res[1] = left - 1;
return res;
}
|
二分法难点主要在边界判断条件的寻找，在上例中，边界条件需要满足两个基本条件：
1.循环最后能退出
2.left 和 right 最后能达到相邻比较程度，需要能覆盖全数组元素
边界判断的难点主要有： 1.起始值和结束值的验证
所以我个人感觉如果写不出很好的边界判断条件的话，优先判断起始值和结束值的情况，可能也是一种行之有效的方案
（算法果然还是太难了…
求平方根
描述
实现 int sqrt(int x) 函数。
计算并返回 x 的平方根，其中 x 是非负整数。
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
69. x 的平方根
分析
x 的平方根一定是在 0-x 的区间内，所以我们可以使得 left=0，right=x，使用二分法去逼近 x^1/2
每次判断条件即 mid*mid 和 x 的比较大小
解题
方法一：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| mySqrt(x) {
let left = 0,
right = x;
while (left <= right) {
let mid = Math.floor((left + right) / 2);
if (mid * mid < x) {
left = mid + 1;
} else if (mid * mid > x) {
right = mid - 1;
} else if (mid * mid === x) {
return mid;
}
}
return right;
}
|
方法二：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| mySqrt(x) {
let left = 0,
right = x + 1;
while (left < right) {
let mid = Math.floor((left + right) / 2);
if (mid * mid < x) {
left = mid + 1;
} else if (mid * mid > x) {
right = mid;
} else if (mid * mid === x) {
return mid;
}
}
return left - 1;
}
|
备注
关于二分法的一些边界判断分析：
关于二分法的一些分析
