Skip to content

Instantly share code, notes, and snippets.

@demoth
Last active December 23, 2015 12:19
Show Gist options
  • Save demoth/6635003 to your computer and use it in GitHub Desktop.
Save demoth/6635003 to your computer and use it in GitHub Desktop.
// 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'
}
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
}
}
}
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