Binary Search Algorithm
Tracking the color of each node necessitates only 1 bit of information per node because there are only two colors. In computer science, a red – black tree is a kind of self-balancing binary search tree. In a 1978 paper," A Dichromatic Framework for Balanced Trees", Leonidas J. Guibas and Robert Sedgewick derived the red-black tree from the symmetric binary B-tree. Sedgewick originally allowed nodes whose two children are red, make his trees more like 2-3-4 trees, but later this restriction was added, make new trees more like 2-3 trees. These trees maintained all paths from root to leaf with the same number of nodes, make perfectly balanced trees.
import java.util.*
/**
* Created by gazollajunior on 03/04/16.
*/
fun <T: Comparable<T>> binarySearch(list: List<T>, key: T): Int? {
var rangeStart = 0
var rangeEnd = list.count()
while (rangeStart < rangeEnd) {
val midIndex = rangeStart + (rangeEnd - rangeStart)/2
if (list[midIndex] == key) {
return midIndex
} else if (list[midIndex] < key) {
rangeStart = midIndex + 1
} else {
rangeEnd = midIndex
}
}
return null
}
fun <T: Comparable<T>> binarySearchRec(list: List<T>, key: T): Optional<Int> {
require(list == list.sorted())
fun helper(start: Int, end: Int): Optional<Int> {
val mid: Int = start + (end - start) / 2
if (end < start) return Optional.empty()
if (key == list[mid]) {
return Optional.of(mid)
} else if (key < list[mid]) {
return helper(start, mid - 1)
} else {
return helper(mid + 1, end)
}
}
return helper(0, list.count())
}
fun main(args: Array<String>) {
println("\nOrdered list:")
val ordered = listOf("Adam", "Clark", "John", "Tim", "Zack")
println(ordered)
val name = "John"
println("\n$name is in the position ${binarySearch(ordered, name)} in the ordered List.")
println("\n$name is in the position ${binarySearchRec(ordered, name)} in the ordered List.")
}
