二分法
二分法又可以被称为二分查找，它描述了在有序集合中搜索特定值的过程。广义的二分查找是将问题的规模尽可能的缩小到原有的一半。
二分查找（非递归实现）
var searchRange = function (nums, target) {
let start = 0, end = nums.length - 1
while (start <= end) {
let mid = Math.floor((start + end) / 2)
if (nums[mid] == target) {
return mid
} else if (nums[mid] > target) {
end = mid - 1
} else if(nums[mid] < target){
start = mid + 1
}
}
return -1
};
二分查找（递归实现）
var searchRange = function (nums, target) {
let start = 0, end = nums.length - 1
let mid = - 1
// 递归函数体，也可以封装最外层函数，就是递归传的参数多一点
function df(start, end) {
// 递归终止条件
if (start > end) return -1
mid = Math.floor((start + end) / 2)
if (nums[mid] == target) {
return mid
} else if (nums[mid] > target) {
df(start, mid - 1)
} else if (nums[mid] < target) {
df(mid + 1, end)
}
}
df(start, end)
return mid
}
二分排序
复杂度分析
- 平均时间复杂度： O(logN)
- 最坏时间复杂度： O(logN)
- 最优时间复杂度： O(1)
推荐文章
你真的会写二分查找吗？
经典例题
1 求数组中的最大元素的二分递归算法
let a =[4,6,7,8]
function solution(a,l,r){
let mid = Math.floor((l+r)/2),max1,max2
if(l<r){
max1 = solution(a,l,mid)
max2 = solution(a,mid+1,r)
return (max1>max2)?max1:max2
}else return a[l];
}
console.log(solution(a,0,3));
2 快排
选定一个基准数，要使得基数的左边的数字全部小于它，右边的数字全部大于它。分别设i和j从左右开始寻找，从左边找到第一个比基数大的数，从右边找到第一个比基数小的数，然后交换这两个数。当i和j相遇时，交换基数和i。再以同样的方式处理两边的数组。
const quickSort = (arr, s, e) => {
if (arr.length <= 1) return
if (s >= e) return
let p = arr[s]
let i = s
let j = e
while (i != j) {
while (arr[j] >= p && i < j) {
j--
}
while (arr[i] <= p && i < j) {
i++
}
if (i < j) {
let temp = arr[i]
arr[i] = arr[j]
arr[j] = temp
}
}
arr[s] = arr[i]
arr[i] = p
quickSort(arr, s, i - 1)
quickSort(arr, i + 1, e)
}
var arr = [6, 1, 2, 7, 9, 3, 4, 5, 10, 8]
quickSort(arr, 0, arr.length - 1)
console.log(arr)
3.二路归并排序
转载详解
力扣习题
力扣704：二分查找
力扣278：第一个错误版本
