Dia 59/2019 - Algoritmos em JS: Pesquisando

Desafio #92daysofcode que fiz no final de 2019. Nesse artigo temos o dia 59, mostrando o uso de algoritmo de pesquisa.

Código

1
2
3
const swap = (array, a, b) => {
[array[a], array[b]] = [array[b], array[a]];
}
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
const partition = (array, left, right) => {
const pivot = array[Math.floor((right + left) / 2)];
let i = left;
let j = right;

while (i <= j) {
while (array[i] < pivot) {
i++;
}
while (array[j] > pivot) {
j--;
}
if (i <= j) {
swap(array, i, j);
i++;
j--;
}
}
return i;
}

const quick = (array, left, right) => {
let index;
if (array.length > 1) {
index = partition(array, left, right);
if (left < index - 1) {
quick(array, left, index - 1);
}
if (index < right) {
quick(array, index, right);
}
}
return array;
}

const quickSort = array => {
return quick(array, 0, array.length - 1);
}
1
2
3
4
5
6
7
8
9
const linearSearch = (array, value) => {
for (let i = 0; i < array.length; i++) {
if (value === array[i]) {
return i;
}
}

return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
const binarySearch = (array, value) => {
const sortedArray = quickSort(array);
let low = 0;
let high = sortedArray.length - 1;

while (low <= high) {
const mid = Math.floor((low + high) / 2);
const element = sortedArray[mid];

if (element < value) {
low = mid + 1;
} else if (element > value) {
high = mid - 1;
} else {
return mid;
}
}

return -1;
}
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
const interpolationSearch = (array, value) => {
const { length } = array;
const lesserEquals = (a, b) => a < b || a === b;
const biggerEquals = (a, b) => a > b || a === b;
const diffFn = (a, b) => Number(a) - Number(b);
let low = 0;
let high = length - 1;
let position = -1;
let delta = -1;

while (low <= high && biggerEquals(value, array[low]) && lesserEquals(value, array[high])) {
delta = diffFn(value, array[low]) / diffFn(array[high], array[low]);
position = low + Math.floor((high - low) * delta);

if (array[position] === value) {
return position;
}

if (array[position] < value) {
low = position + 1;
} else {
high = position - 1;
}
}

return -1;
}
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
const findMaxValue = array => {
if (array && array.length > 0) {
let max = array[0];
for (let i = 1; i < array.length; i++) {
if (max < array[i]) {
max = array[i];
}
}

return max;
}

return undefined;
}

const findMinValue = array => {
if (array && array.length > 0) {
let min = array[0];
for (let i = 1; i < array.length; i++) {
if (min > array[i]) {
min = array[i];
}
}

return min;
}

return undefined;
}
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
const jumpSearch = (sortedArray, seekElement) => {
const arraySize = sortedArray.length;
const compareFn = (a, b) => {
if (a === b) {
return 0;
}
return a < b ? -1 : 1;
}

if (!arraySize) {
return -1;
}

const jumpSize = Math.floor(Math.sqrt(arraySize));
let blockStart = 0;
let blockEnd = jumpSize;

while (compareFn(seekElement, sortedArray[Math.min(blockEnd, arraySize) - 1]) > 0) {
blockStart = blockEnd;
blockEnd += jumpSize;

if (blockStart > arraySize) {
return -1;
}
}

let currentIndex = blockStart;

while (currentIndex < Math.min(blockEnd, arraySize)) {
if (compareFn(sortedArray[currentIndex], seekElement) === 0) {
return currentIndex;
}

currentIndex += 1;
}

return -1;
}
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
// https://www.geeksforgeeks.org/searching-algorithms/
// https://www.tutorialspoint.com/introduction-to-searching-algorithms
// https://pt.wikipedia.org/wiki/Algoritmo_de_busca

// https://en.wikipedia.org/wiki/Linear_search
// https://pt.wikipedia.org/wiki/Pesquisa_bin%C3%A1ria
/*
* Linear Search (Sequencial Search)
***********************************/
const ls = [2, 5, 3, 7, 8, 10, 15, 18, 24, 111, 12];
console.log(linearSearch(ls, 15));
// 6
console.log(linearSearch(ls, 24));
// 8
console.log('------------------------------------------------');

// https://en.wikipedia.org/wiki/Binary_search_algorithm
// https://wiki.portugal-a-programar.pt/algoritmo:pesquisa_binaria
/*
* Binary Search
***********************************/
console.log(binarySearch([1, 3, 5, 7, 9], 3));
// 1
console.log('------------------------------------------------');

// https://en.wikipedia.org/wiki/Interpolation_search
/*
* Interpolation Search
***********************************/
const is = [2, 6, 8, 12, 14, 16, 20, 24, 26, 28, 30, 31, 35];
console.log(interpolationSearch(is, 12));
// 3
console.log(interpolationSearch(is, 35));
// 12
console.log('------------------------------------------------');

/*
* Min & Max Search
***********************************/
console.log(findMaxValue([101,12,30,46,52,6]));
// 101
console.log(findMinValue([10,21,3,42,50,36]));
// 3
console.log('------------------------------------------------');

// https://en.wikipedia.org/wiki/Jump_search
//
/*
* Jump Search
***********************************/
const js = [2, 6, 8, 12, 43, 78, 99, 134, 144, 156, 199, 256, 500];
console.log(jumpSearch(js, 256));
// 11
console.log(jumpSearch(js, 2));
// 0
console.log('------------------------------------------------');

Conclusão

A postagem original pode ser vista no meu Instagram e o código está acessível no meu Github.

Relacionados

Ao fechar este aviso ou continuar navegando no site Nerd Calistênico, você aceita o uso de cookies.

Este site usa cookies para assegurar a melhor experiência para os nossos usuários. Consulte nossa política de privacidade.

Uma nova versão está disponível. Clique aqui para atualizar.