algorithm/binarySearch.js at master · springuper/algorithm · GitHub

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
var assert = require('assert');

/**
 * 二分查找-左闭右闭型
 * @method binarySearch
 * @param {Array} arr 按升序排列
 * @param {Number} num
 * @return {Number}
 */
function binarySearch(arr, num) {
    var from = 0,
        to = arr.length - 1,
        mid;

    while (from <= to) {
        mid = Math.floor((from + to) / 2);
        if (arr[mid] > num) {
            to = mid - 1;
        } else if (arr[mid] < num) {
            from = mid + 1;
        } else {
            return mid;
        }
    }

    return -1;
}

/**
 * 二分查找-左闭右开型
 * @method binarySearchRightOpen
 * @param {Array} arr 按升序排列
 * @param {Number} num
 * @return {Number}
 */
function binarySearchRightOpen(arr, num) {
    var start = 0,
        end = arr.length,
        mid;

    while (start < end) {
        mid = Math.floor((start + end) / 2);
        if (arr[mid] > num) {
            end = mid;
        } else if (arr[mid] < num) {
            start = mid + 1;
        } else {
            return mid;
        }
    }

    return -1;
}

/**
 * 二分查找-重复值取最左角标
 * @method binarySearch
 * @param {Array} arr 按升序排列
 * @param {Number} num
 * @return {Number}
 */
function binarySearchMinimum(arr, num) {
    var from = 0,
        to = arr.length - 1,
        mid;

    while (from <= to) {
        mid = Math.floor((from + to) / 2);
        if (arr[mid] >= num) {
            to = mid - 1;
        } else {
            from = mid + 1;
        }
    }

    if (arr[to + 1] === num) {
        return to + 1;
    }

    return -1;
}

var arr = [1, 2, 3, 4, 5];
var arrDuplicate = [1, 2, 2, 2, 5];
var arrEqual = [2, 2, 2, 2];
assert.deepEqual(binarySearch(arr, 0), -1);
assert.deepEqual(binarySearch(arr, 1), 0);
assert.deepEqual(binarySearch(arr, 2), 1);
assert.deepEqual(binarySearch(arr, 3), 2);
assert.deepEqual(binarySearch(arr, 5), 4);
assert.deepEqual(binarySearch(arr, 15), -1);
assert.deepEqual(binarySearchRightOpen(arr, 0), -1);
assert.deepEqual(binarySearchRightOpen(arr, 1), 0);
assert.deepEqual(binarySearchRightOpen(arr, 2), 1);
assert.deepEqual(binarySearchRightOpen(arr, 3), 2);
assert.deepEqual(binarySearchRightOpen(arr, 5), 4);
assert.deepEqual(binarySearchRightOpen(arr, 15), -1);
assert.deepEqual(binarySearchMinimum(arrDuplicate, 0), -1);
assert.deepEqual(binarySearchMinimum(arrDuplicate, 1), 0);
assert.deepEqual(binarySearchMinimum(arrDuplicate, 2), 1);
assert.deepEqual(binarySearchMinimum(arrDuplicate, 5), 4);
assert.deepEqual(binarySearchMinimum(arrDuplicate, 6), -1);
assert.deepEqual(binarySearchMinimum(arrEqual, 2), 0);