二分查找

二分查找
输入：[-1,0,3,4,6,10,13,14],13
返回值：6
方法：先与mid比较，如果比mid大，则left更新，否则right更新

function search(nums, target) {
    let start = 0, end = nums.length - 1
    while (start <= end) {
        let mid = start + Math.floor((end - start) / 2)
        if (nums[mid] > target) {
            end = mid - 1
        } else if (nums[mid] < target) {
            start = mid + 1
        } else {
            return mid
        }
    }
    return -1
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

二维矩阵

搜索二维矩阵

搜索二维矩阵
输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出：true
方法：将二维矩阵变成一维，然后使用基础版二分查找

function Find(target, array) {
    // write code here
    let rows = array.length, cols = array[0].length
    let low = 0, high = rows * cols - 1
    while (low <= high) {
        let mid = low + Math.floor((high - low) / 2)
        // 确定mid在二维矩阵中的位置
        let x = array[Math.floor(mid / cols)][mid % cols]
        console.log("mid, x", mid, x);
        if (x < target) {
            low = mid + 1
        } else if (x > target) {
            high = mid - 1
        } else {
            return true
        }
    }
    return false
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

二维数组中的查找

二维数组中的查找
下一行的第一个数组不比上一行的最后一个数字大，每行递增、每列递增
输入：7,[[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]
返回值：true
方法：以二维矩阵的左下角为零点，如果target大于它，则向右移，否则向上移

function Find(target, array) {
    // write code here
    // 二维数组左下角为零点
    let rows = array.length
    let start = 0, row = rows - 1
    while (array[row] && array[row][start]) {
        if (array[row][start] < target) {
            start++
        } else if (array[row][start] > target) {
            row--
        } else {
            return true
        }
    }
    return false
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

寻找峰值

寻找峰值
输入：[2,4,1,2,7,8,4]
返回值：1
说明：4和8都是峰值元素，返回4的索引1或者8的索引5都可以
方法：mid小于mid+1，往上走，重合时是峰值

function findPeakElement(nums) {
    let start = 0, end = nums.length - 1
    while (start < end) {
        let mid = start + Math.floor((end - start) / 2)
        // mid小于mid+1，往上走
        // 重合时时峰值
        if (nums[mid] < nums[mid + 1]) {
            start = mid + 1
        } else {
            end = mid
        }
    }
    return start
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

数组中的逆序对

数组中的逆序对
输入：[1,2,3,4,5,6,7,0]
返回值：7
方法：利用归并的两两比较，在比较过程中计算逆序对

function InversePairs(data) {
    // write code here
    // 利用归并，在排序中计算逆序对
    let sum = 0
    mergeSort(data)
    return sum

    function mergeSort(nums) {
        if (nums.length < 2) return nums
        let mid = Math.floor(nums.length / 2)
        let left = nums.slice(0, mid)
        let right = nums.slice(mid)
        return merge(mergeSort(left), mergeSort(right))
    }
    function merge(left, right) {
        let res = []
        let leftLen = left.length, rightLen = right.length
        let len = leftLen + rightLen
        for (let index = 0, i = 0, j = 0; index < len; index++) {
            if (i >= leftLen) {
                res[index] = right[j++]
            } else if (j >= rightLen) {
                res[index] = left[i++]
            } else if (left[i] <= right[j]) {
                res[index] = left[i++]
            } else {
                res[index] = right[j++]
                // 比归并多的一行代码
                sum += leftLen - i
                console.log(sum, leftLen,i);
            }
        }
        return res
    }
}
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