/
KarateChop.scala
119 lines (100 loc) · 2.24 KB
/
KarateChop.scala
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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
object KarateChop {
def chop (target: Int, searchBox: Array[Int]) : Int = {
val size = searchBox.size
if (size == 0) {
return -1
}
if (size == 1){
if(searchBox(0) == target){
return 0
} else {
return -1
}
}
val pointer = searchBox.size / 2
val searchResult = searchBox(pointer)
if(searchResult == target){
return pointer
}
if (searchResult < target){
val partialResult = chop(target, searchBox.slice(pointer, size))
if(partialResult == -1)
return -1
return pointer + partialResult
}
if (searchResult > target){
return chop(target, searchBox.slice(0, pointer));
}
return -1
}
def assert(expected: Int, actual: Int){
if(expected == actual){
println("OK");
}
else {
println("Error, expected: " + expected + " actual: "+ actual);
}
}
def main(args: Array[String]){
test1()
test2()
test3()
test4()
test5()
test6()
test7()
test8()
test9()
test10()
}
def test1(): Unit ={
val target = 2
val searchBox = Array.emptyIntArray
assert(-1, chop(target, searchBox))
}
def test2(): Unit ={
val target = 1
val searchBox = Array(1,2,3,4,5)
assert(0, chop(target, searchBox))
}
def test3(): Unit ={
val target = 3
val searchBox = Array(1,2,3,4,5)
assert(2, chop(target, searchBox))
}
def test4(): Unit ={
val target = 3
val searchBox = Array(1,2,3)
assert(2, chop(target, searchBox))
}
def test5(): Unit ={
val target = 1
val searchBox = Array(1)
assert(0, chop(target, searchBox))
}
def test6(): Unit ={
val target = 5
val searchBox = Array(1,2,3,4,5)
assert(4, chop(target, searchBox))
}
def test7(): Unit ={
val target = 4
val searchBox = Array(1,2,3,4,5)
assert(3, chop(target, searchBox))
}
def test8(): Unit ={
val target = 2
val searchBox = Array(1,2,3,4,5)
assert(1, chop(target, searchBox))
}
def test9(): Unit ={
val target = 0
val searchBox = Array(1,2,3,4,5)
assert(-1, chop(target, searchBox))
}
def test10(): Unit ={
val target = 7
val searchBox = Array(1,2,3,4,5)
assert(-1, chop(target, searchBox))
}
}