Last active
August 8, 2024 17:20
-
-
Save rkt2spc/a003f0dfcb9a9cdeb1146f9edd34e48c to your computer and use it in GitHub Desktop.
Benchmark Binary Search and Linear Search on small array
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| package main | |
| import ( | |
| "fmt" | |
| "math/rand" | |
| "testing" | |
| ) | |
| func linearSearch(arr []int, value int) int { | |
| for i, v := range arr { | |
| if v == value { | |
| return i | |
| } | |
| } | |
| return -1 | |
| } | |
| func binarySearch(arr []int, value int) int { | |
| l := 0 | |
| r := len(arr) - 1 | |
| for l <= r { | |
| m := l + (r-l)/2 | |
| if arr[m] > value { | |
| r = m - 1 | |
| } else if arr[m] < value { | |
| l = m + 1 | |
| } else { | |
| return m | |
| } | |
| } | |
| return -1 | |
| } | |
| func genArr(size int) []int { | |
| res := make([]int, size) | |
| prev := rand.Intn(10) | |
| for i := range res { | |
| res[i] = prev + rand.Intn(10) | |
| prev = res[i] | |
| } | |
| return res | |
| } | |
| func BenchmarkSearch(b *testing.B) { | |
| arr := genArr(1024) | |
| // random positions | |
| idxs := make([]int, 10) | |
| for i := range idxs { | |
| idxs[i] = rand.Intn(len(arr)) | |
| } | |
| for _, idx := range idxs { | |
| b.Run(fmt.Sprintf("linear search [%d]", idx), func(b *testing.B) { | |
| got := linearSearch(arr, arr[idx]) | |
| if got != idx { | |
| b.Fail() | |
| } | |
| }) | |
| b.Run(fmt.Sprintf("binary search [%d]", idx), func(b *testing.B) { | |
| got := binarySearch(arr, arr[idx]) | |
| if got != idx { | |
| b.Fail() | |
| } | |
| }) | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment