Repository navigation
Expand file tree
/
Copy pathlinearSearch.go
More file actions
105 lines (85 loc) · 2.47 KB
/
Copy pathlinearSearch.go
File metadata and controls
105 lines (85 loc) · 2.47 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
/*
An implementation of a simple linear search (brute force) algorithm.
*/
package main
import (
"fmt"
"math/rand"
"strconv"
"time"
)
func main() {
// Get the number of items and maximum item value.
var num_items, max int;
fmt.Printf("# Items: ")
fmt.Scanln(&num_items)
fmt.Printf("Max: ")
fmt.Scanln(&max)
// Make and display the slice of random ints.
values := makeRandomSlice(num_items, max)
printSlice(values, 40)
fmt.Println()
target := ""
var index, numTests int
// Loop to find target values.
for {
fmt.Printf("Target: ")
fmt.Scanln(&target)
// If input is just a newline (empty string) break the loop.
if target == "" {
break
}
itarget, err := strconv.Atoi(target)
if err != nil {
fmt.Println("error: ", err)
fmt.Println("Please enter an integer.")
target = ""
continue
}
index, numTests = linearSearch(values, itarget)
if index >= 0 {
fmt.Print("Target found at values[", index, "] after ", numTests, " tests.\n")
} else {
fmt.Println("Target not found after", numTests, "tests.")
}
// reset target value
target = ""
}
}
// Searches the values slice from the beginning for target.
// Returns the index of target (or -1 if not found) and the number of tests required.
func linearSearch(values []int, target int) (index, numTests int) {
for i := 0; i < len(values); i++ {
numTests++
if values[i] == target {
index = i
return index, numTests
}
}
// Failed to find target.
index = -1
return index, numTests
}
/* Utility functions. */
// Returns a slice of numItems random ints, up to max.
func makeRandomSlice(numItems, max int) []int {
// We are calling this an array, but it's actually a slice.
arr := make([]int, numItems)
// Seed the random number generator, otherwise it will generate the same set.
rand.Seed(time.Now().UnixNano())
for i := 0; i < numItems; i++ {
arr[i] = rand.Intn(max)
}
return arr
}
// Prints the first numItems of the slice arr.
func printSlice(arr []int, numItems int) {
if (len(arr) < numItems) {
numItems = len(arr)
}
fmt.Print("[ ")
for i := 0; i < numItems; i++ {
fmt.Print(arr[i], " ")
}
fmt.Print("]\n")
}