二分查找

发表于 | 分类于

二分查找基本(当有重复元素时，位置不固定)

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
function binarySearch(list, target) {
    if (list.length === 0) {
        return -1;
    }
    let start = 0,
        end = list.length - 1,
        mid;
    while (start + 1 < end) {
        mid = start + Math.floor((end - start) / 2);
        console.log(start, mid, end);

        if (list[mid] === target) {
            return mid;
        }
        if (list[mid] > target) {
            end = mid;
        } else {
            start = mid;
        }
        if (list[start] === target) {
            return start;
        }
        if (list[end] === target) {
            return end;
        }
    }
}

let testlist = [0, 1, 2, 3, 3, 3, 3, 8, 13, 17, 19, 32, 42];

console.log(binarySearch(testlist, 3));

二分查找，最前、最后元素

  1. list[mid] === target时不再直接返回位置，而是继续查找
  2. 如果找last，则start= mid, 找first，则 end = mid
  3. 如果结果是[3,3,3],如果找first则先判断start，找last则先判断end
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
//以找last为例
function binarySearch(list, target, pos) {
    if (list.length === 0) {
        return -1;
    }
    let start = 0,
        end = list.length - 1,
        mid;
    while (start + 1 < end) {
        //最终[start,mid,end]
        mid = start + Math.floor((end - start) / 2);
        if (list[mid] === target) {//mid时不再直接返回
            if (pos === 'last') {
                start = mid; //继续找
            } else if (pos === 'first') {
                end = mid; //继续找
            } else {
                return mid;
            }
        } else if (list[mid] < target) {
            start = mid;
        } else {
            end = mid;
        }
    }
    if (list[end] === target) {//如果是找last，则先判断end,本例是last
        return end;
    }
    if (list[start] === target) {//如果是找first，则先判断start
        return start;
    }
}

// let dat1 = [ 1, 1, 1, 1,2 ];
// let dat2 = [1];
// let dat3 = [1,2, 2, 2, 2, 2, 2];
// let dat4 = [1, 2, 3, 4, 5, 6];
// let dat5 = [1, 1, 1, 1, 1,2];
let testlist = [0, 1, 2, 3, 3, 3];
console.log(binarySearch(testlist, 3, 'last'));