Last active
December 23, 2015 12:19
-
-
Save demoth/6635003 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// idea specific | |
apply plugin: 'idea' | |
idea{ | |
project{ | |
languageLevel = '1.7' | |
} | |
} | |
apply plugin:'groovy' | |
repositories{ | |
mavenLocal() | |
mavenCentral() | |
} | |
dependencies{ | |
compile 'org.codehaus.groovy:groovy-all:2.1.5' | |
testCompile 'junit:junit:4.10' | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class Finder { | |
/** | |
* Simple Binary search implementation. | |
* Author: Daniil | |
* @param arr - list to search in | |
* @param el - element to find | |
* @return index of the found element, or -1 if there is no such element in | |
* <code>arr</code> or of <code>arr</code> is empty or <code>null</code> | |
*/ | |
static int binarySearch(List arr, int el) { | |
if (arr == null || arr.empty || (arr.size == 1 && arr[0] != el)) | |
return -1 | |
int pivot = (int) arr.size / 2 | |
if (arr[pivot] == el) | |
return pivot | |
else if (el < arr[pivot]) { | |
int search = binarySearch(arr[0..pivot-1], el) | |
return search >= 0 ? search : -1 | |
} else { | |
int search = binarySearch(arr[1 + pivot..arr.size - 1], el) | |
return search >= 0 ? search + pivot + 1 : -1 | |
} | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class FinderTest extends GroovyTestCase { | |
private List list | |
void setUp() { | |
list = [1, 2, 7, 10, 40, 50, 350, 599] | |
} | |
void testBinarySearch1() { | |
assert Finder.binarySearch(list, 1) == 0 | |
} | |
void testBinarySearch2() { | |
assert Finder.binarySearch(list, 2) == 1 | |
} | |
void testBinarySearch3() { | |
assert Finder.binarySearch(list, 7) == 2 | |
} | |
void testBinarySearch4() { | |
assert Finder.binarySearch(list, 10) == 3 | |
} | |
void testBinarySearch5() { | |
assert Finder.binarySearch(list, 40) == 4 | |
} | |
void testBinarySearch6() { | |
assert Finder.binarySearch(list, 50) == 5 | |
} | |
void testBinarySearch7() { | |
assert Finder.binarySearch(list, 350) == 6 | |
} | |
void testBinarySearch8() { | |
assert Finder.binarySearch(list, 599) == 7 | |
} | |
void testNotFound() { | |
assert Finder.binarySearch(list, 0) == -1 | |
} | |
void testEmptyArray() { | |
assert Finder.binarySearch([], 0) == -1 | |
} | |
void testNullArray() { | |
assert Finder.binarySearch(null, 0) == -1 | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment