JavaScriptAlgorithms/Classical algorithm problem/Binary Search.html at master · biaodigit/JavaScriptAlgorithms · 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
<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title>Title</title>
</head>
<body>
<script>
    //    二分查找法，在有序数组中查找target
    //    如果找到target,返回对应的索引index，没有则返回-1
    function binarySearch(arr, target) {
        let n = arr.length - 1
        let [l, r] = [0, n]

        while (l <= r) {
            let mid = l + Math.floor((r - l) / 2);  //防止整型溢出
            if (arr[mid] === target) {
                return mid
            }

            //在arr[l....mid-1]中查找target
            if (target < arr[mid]) {
                r = mid - 1
            } else {
                //在arr[mid+1....r]中查找target
                l = mid + 1
            }
        }
        return -1
    }

    //使用递归实现二分查找
    let binarySearch2 = (arr, target, l = 0, r = arr.length - 1) => {
        let mid = Math.floor(l + (r - l) / 2);
        if (l <= r) {
            if (target === arr[mid]) {
                return mid;
            } else if (target > arr[mid]) {
                return binarySearch2(arr, target, mid + 1, r);
            } else {
                return binarySearch2(arr, target, l, mid - 1);
            }
        }

        return -1;
    }

    console.log(binarySearch([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 10, 4))
    console.log(binarySearch2([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 2))
</script>
</body>
</html>