Skip to content

Commit 9113988

Browse files
64json64json
committed
Merge pull request algorithm-visualizer#1 from nem035/binary-search
Binary search
2 parents 579a518 + 60893cd commit 9113988

File tree

8 files changed

+219
-50
lines changed

8 files changed

+219
-50
lines changed

‎algorithm/category.json

+6
Original file line numberDiff line numberDiff line change
@@ -6,6 +6,12 @@
66
"bfs": "BFS"
77
}
88
},
9+
"search": {
10+
"name": "Search",
11+
"list": {
12+
"binary_search": "Binary Search"
13+
}
14+
},
915
"sorting": {
1016
"name": "Sorting",
1117
"list": {

‎algorithm/search/binary_search/desc.json

+18
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,18 @@
1+
{
2+
"Binary Search": "Binary Search is a search algorithm that finds the position of a target value within a sorted array. It works by comparing the target value to the middle element of the array; if they are unequal, the lower or upper half of the array is eliminated depending on the result and the search is repeated in the remaining subarray until it is successful.",
3+
"Applications": [
4+
"Finding values in a sorted collection",
5+
"Traversing binary search trees"
6+
],
7+
"Complexity": {
8+
"time": "worst O(log(N)), best O(1), average O(log(N))",
9+
"space": "worst O(log(N)) - recursive, O(1) - iterative"
10+
},
11+
"References": [
12+
"<a href='https://en.wikipedia.org/wiki/Binary_search_algorithm'>Wikipedia</a>"
13+
],
14+
"files": {
15+
"recursive": "Recursively searching a sorted array",
16+
"iterative": "Iteratively searching a sorted array"
17+
}
18+
}

‎algorithm/search/binary_search/iterative/code.js

+44
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,44 @@
1+
function BinarySearch(array, element) { // array = sorted array, element = element to be found,
2+
3+
var minIndex = 0;
4+
var maxIndex = array.length - 1;
5+
var currentIndex;
6+
var testElement;
7+
8+
while (minIndex <= maxIndex) {
9+
10+
middleIndex = Math.floor((minIndex + maxIndex) / 2);
11+
testElement = array[middleIndex];
12+
13+
tracer._print('Searching at index: ' + middleIndex);
14+
tracer._notify(middleIndex);
15+
16+
if (testElement < element) {
17+
18+
tracer._print('Going right.');
19+
minIndex = middleIndex + 1;
20+
21+
} else if (testElement > element) {
22+
23+
tracer._print('Going left.');
24+
maxIndex = middleIndex - 1;
25+
26+
} else {
27+
28+
tracer._print(element + ' is found at position ' + middleIndex + '!');
29+
tracer._select(middleIndex);
30+
31+
return middleIndex;
32+
}
33+
}
34+
35+
tracer._print(element + ' is not found!');
36+
return -1;
37+
}
38+
39+
var element = D[0];
40+
41+
tracer._sleep(1000);
42+
tracer._pace(1000);
43+
tracer._print('Using iterative binary search to find ' + element);
44+
BinarySearch(D, element, 0, D.length - 1);

‎algorithm/search/binary_search/iterative/data.js

+3
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,3 @@
1+
var tracer = new Array1DTracer();
2+
var D = Array1D.randomSorted(15, 0, 50);
3+
tracer._setData(D);

‎algorithm/search/binary_search/recursive/code.js

+38
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,38 @@
1+
function BinarySearch(array, element, minIndex, maxIndex) { // array = sorted array, element = element to be found, minIndex = minIndex index, maxIndex = maxIndex index
2+
if (minIndex > maxIndex) {
3+
tracer._print(element + ' is not found!');
4+
return -1;
5+
}
6+
7+
var middleIndex = Math.floor((minIndex + maxIndex) / 2);
8+
var testElement = array[middleIndex];
9+
10+
tracer._print('Searching at index: ' + middleIndex);
11+
tracer._notify(middleIndex);
12+
13+
if (testElement < element) {
14+
tracer._print('Going right.');
15+
return BinarySearch(array, element, middleIndex + 1, maxIndex);
16+
}
17+
18+
if (testElement > element) {
19+
tracer._print('Going left.');
20+
return BinarySearch(array, element, minIndex, middleIndex - 1);
21+
}
22+
23+
if (testElement === element) {
24+
tracer._print(element + ' is found at position ' + middleIndex + '!');
25+
tracer._select(middleIndex);
26+
return middleIndex;
27+
}
28+
29+
tracer._print(element + ' is not found!');
30+
return -1;
31+
}
32+
33+
var element = D[0];
34+
35+
tracer._sleep(1000);
36+
tracer._pace(1000);
37+
tracer._print('Using binary search to find ' + element);
38+
BinarySearch(D, element, 0, D.length - 1);

‎algorithm/search/binary_search/recursive/data.js

+3
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,3 @@
1+
var tracer = new Array1DTracer();
2+
var D = Array1D.randomSorted(15, 0, 50);
3+
tracer._setData(D);

‎js/module/array1d.js

+20-11
Original file line numberDiff line numberDiff line change
@@ -6,18 +6,21 @@ Array1DTracer.prototype = Object.create(Array2DTracer.prototype);
66
Array1DTracer.prototype.constructor = Array1DTracer;
77

88
var Array1D = {
9-
random: function (N, min, max) {
9+
random: function(N, min, max) {
1010
return Array2D.random(1, N, min, max)[0];
11+
},
12+
randomSorted: function(N, min, max) {
13+
return Array2D.randomSorted(1, N, min, max)[0];
1114
}
1215
};
1316

1417
// Override
15-
Array1DTracer.prototype._setData = function (D) {
18+
Array1DTracer.prototype._setData = function(D) {
1619
return Array2DTracer.prototype._setData.call(this, [D]);
1720
};
1821

1922
// Override
20-
Array1DTracer.prototype._notify = function (idx1, idx2) {
23+
Array1DTracer.prototype._notify = function(idx1, idx2) {
2124
if (idx2 === undefined) {
2225
Array2DTracer.prototype._notify.call(this, 0, idx1);
2326
} else {
@@ -26,7 +29,7 @@ Array1DTracer.prototype._notify = function (idx1, idx2) {
2629
};
2730

2831
// Override
29-
Array1DTracer.prototype._select = function (s, e) {
32+
Array1DTracer.prototype._select = function(s, e) {
3033
if (e === undefined) {
3134
Array2DTracer.prototype._select.call(this, 0, s);
3235
} else {
@@ -35,16 +38,19 @@ Array1DTracer.prototype._select = function (s, e) {
3538
};
3639

3740
// Override
38-
Array1DTracer.prototype._selectSet = function (indexes) {
41+
Array1DTracer.prototype._selectSet = function(indexes) {
3942
var coords = [];
40-
indexes.forEach(function (index) {
41-
coords.push({x: 0, y: index});
43+
indexes.forEach(function(index) {
44+
coords.push({
45+
x: 0,
46+
y: index
47+
});
4248
});
4349
Array2DTracer.prototype._selectSet.call(this, coords);
4450
};
4551

4652
// Override
47-
Array1DTracer.prototype._deselect = function (s, e) {
53+
Array1DTracer.prototype._deselect = function(s, e) {
4854
if (e === undefined) {
4955
Array2DTracer.prototype._deselect.call(this, 0, s);
5056
} else {
@@ -53,10 +59,13 @@ Array1DTracer.prototype._deselect = function (s, e) {
5359
};
5460

5561
// Override
56-
Array1DTracer.prototype._deselectSet = function (indexes) {
62+
Array1DTracer.prototype._deselectSet = function(indexes) {
5763
var coords = [];
58-
indexes.forEach(function (index) {
59-
coords.push({x: 0, y: index});
64+
indexes.forEach(function(index) {
65+
coords.push({
66+
x: 0,
67+
y: index
68+
});
6069
});
6170
Array2DTracer.prototype._deselectSet.call(this, coords);
6271
};

0 commit comments

Comments
 (0)