Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit2be287f

Browse files
committed
Added binary search algorithm
1 parent579a518 commit2be287f

File tree

6 files changed

+166
-50
lines changed

6 files changed

+166
-50
lines changed

‎algorithm/category.json‎

Lines changed: 6 additions & 0 deletions
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": {
Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,17 @@
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+
}
17+
}
Lines changed: 33 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,33 @@
1+
functionBinarySearch(array,element,minIndex,maxIndex){// array = sorted array, element = element to be found, minIndex = minIndex index, maxIndex = maxIndex index
2+
varmiddleIndex=Math.floor((minIndex+maxIndex)/2);
3+
vartestElement=array[middleIndex];
4+
5+
tracer._print('Searching at index: '+middleIndex);
6+
tracer._notify(middleIndex);
7+
8+
if(testElement<element){
9+
tracer._print('Going right.');
10+
returnBinarySearch(array,element,middleIndex+1,maxIndex);
11+
}
12+
13+
if(testElement>element){
14+
tracer._print('Going left.');
15+
returnBinarySearch(array,element,minIndex,middleIndex-1);
16+
}
17+
18+
if(testElement===element){
19+
tracer._print(element+' is found at position '+middleIndex+'!');
20+
tracer._select(middleIndex);
21+
returnmiddleIndex;
22+
}
23+
24+
tracer._print(element+' is not found!');
25+
return-1;
26+
}
27+
28+
varelement=D[0];
29+
30+
tracer._sleep(1000);
31+
tracer._pace(1000);
32+
tracer._print('Using binary search to find '+element);
33+
BinarySearch(D,element,0,D.length-1);
Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,3 @@
1+
vartracer=newArray1DTracer();
2+
varD=Array1D.randomSorted(15,0,50);
3+
tracer._setData(D);

‎js/module/array1d.js‎

Lines changed: 20 additions & 11 deletions
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
varArray1D={
9-
random:function(N,min,max){
9+
random:function(N,min,max){
1010
returnArray2D.random(1,N,min,max)[0];
11+
},
12+
randomSorted:function(N,min,max){
13+
returnArray2D.randomSorted(1,N,min,max)[0];
1114
}
1215
};
1316

1417
// Override
15-
Array1DTracer.prototype._setData=function(D){
18+
Array1DTracer.prototype._setData=function(D){
1619
returnArray2DTracer.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
varcoords=[];
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
varcoords=[];
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)
[8]ページ先頭
©2009-2025 Movatter.jp