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.
package BinarySearch
import (
"math/rand"
"testing"
"time"
)
func BinarySearch(array []int, number int) int {
minIndex := 0
maxIndex := len(array) - 1
for minIndex <= maxIndex {
midIndex := int((maxIndex + minIndex) / 2)
midItem := array[midIndex]
if number == midItem {
return midIndex
}
if midItem < number {
minIndex = midIndex + 1
} else if midItem > number {
maxIndex = midIndex - 1
}
}
return -1
}
func SortArray(array []int) {
for itemIndex, itemValue := range array {
for itemIndex != 0 && array[itemIndex-1] > itemValue {
array[itemIndex] = array[itemIndex-1]
itemIndex -= 1
}
array[itemIndex] = itemValue
}
}
func TestBinarySearch(t *testing.T) {
random := rand.New(rand.NewSource(time.Now().UnixNano()))
array := make([]int, random.Intn(100-10)+10)
for i := range array {
array[i] = random.Intn(100)
}
SortArray(array)
for _, value := range array {
result := BinarySearch(array, value)
if result == -1 {
t.Fail()
}
}
}
