xsnippet logotype

xsnippet

#363697, Untitled [ JavaScript ]

by Guest
 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
function generateSortedArray(length) {
  let foo = [];
  for (let i = 1; i <= length; i++) { foo.push(i + 3); }
  return foo;
}

//var values2 = [1, 7, 12, 19, 23, 25, 34, 67, 78, 99, 112, 113];

function binarySearch(array, value) {
  let start = 0;
  let end = array.length - 1;
  
  while (start <= end) {
    let center = Math.floor((start + end) / 2);
  	let prediction = array[center];

    if (prediction === value) {
    	return center;
    }

    if (prediction > value) {
    	end = center - 1;
    } else if (prediction < value) {
    	start = center + 1;
    }
  }
  
  return null;
}

function linearSearch(array, value) {
  for (let i = 0; i < array.length; i++) {
    if (array[i] === value) {
      return i;
    }
  }
}

var value10000 = generateSortedArray(10000);
var value100000 = generateSortedArray(100000);
var value1000000 = generateSortedArray(1000000);


binarySearch(value10000, 100)
linearSearch(value10000, 100)

//console.log(binarySearch(value10000, 8134));  // should be 2
//console.log(linearSearch(value10000, 8134));  // should be 2

console.time('binarySearch');
binarySearch(value10000, 8134)
console.timeEnd('binarySearch');

console.time('linearSearch');
linearSearch(value10000, 8134)
console.timeEnd('linearSearch');


console.time('binarySearch2');
binarySearch(value100000, 81340)
console.timeEnd('binarySearch2');

console.time('linearSearch2');
linearSearch(value100000, 81340)
console.timeEnd('linearSearch2');


console.time('binarySearch3');
binarySearch(value1000000, 813400)
console.timeEnd('binarySearch3');

console.time('linearSearch3');
linearSearch(value1000000, 813400)
console.timeEnd('linearSearch3');