Linked lists are linear data structures that hold data in individual objects called nodes. These nodes hold both the data and a reference to the next node in the list. Linked lists are often used because of their efficient insertion and deletion. They can be used to implement stacks, queues, and other abstract data types
Category: Linear
Linear data structures are lists, sets, tuples, queues, stacks, and heaps.
The time complexity of this algorithm is in the order of O(log n).
The binary search algorithm compares the input value to the middle element of the sorted collection.
// Binary Search
package main
// importing sort package
import (
"fmt"
"sort"
)
// main method
func main() {
var elements []int
elements = []int{1, 3, 16, 10, 28, 31, 36, 45, 75}
var element int
element = 36
var i int
i = sort.Search(len(elements), func(i int) bool { return elements[i] >= element })
if i < len(elements) && elements[i] == element {
fmt.Printf("found element %d at index %d in %v\n", element, i, elements)
} else {
fmt.Printf("element %d not found in %v\n", element, elements)
}
}func Search(n int, f func(int) bool) int
Search uses binary search to find and return the smallest index i in [0, n) at which f(i) is true, assuming that on the range [0, n), f(i) == true implies f(i+1) == true.
When shifting right with a logical right shift ( >> ), the least-significant bit is lost and a 0 is inserted on the other end. For positive numbers, a single logical right shift divides a number by 2, throwing out any remainders.
func Search(n int, f func(int) bool) int {
// Define f(-1) == false and f(n) == true.
// Invariant: f(i-1) == false, f(j) == true.
i, j := 0, n
for i < j {
h := int(uint(i+j) >> 1) // avoid overflow when computing h
// i ≤ h < j
if !f(h) {
i = h + 1 // preserves f(i-1) == false
} else {
j = h // preserves f(j) == true
}
}
// i == j, f(i-1) == false, and f(j) (= f(i)) == true => answer is i.
return i
}
Categories
Linear Search
The time complexity of the linear search algorithm is O(n). This means that the running time increases at most linearly with the size of the input.
// Linear Search
package main
import (
"fmt"
)
// Linear Search function
func LinearSearch(elements []int, findElement int) bool {
var element int
for _, element = range elements {
if element == findElement {
return true
}
}
return false
}
func main() {
var elements []int
elements = []int{15, 48, 26, 18, 41, 86, 29, 51, 20}
fmt.Println(LinearSearch(elements, 48))
}