ua-nick/data-structures-and-algorithms

Data Structures and Algorithms implementation in Go

data-structures-and-algorithms's Issues

func RemoveByValue in doublylinkedlist.go may have one problem

the block as below

current := list.head
	for current.next != nil {
		if current.next.data == i {
			if current.next.next != nil {
				current.next.next.prev = current
			}
			current.next = current.next.next
			return true
		}
		current = current.next
	}

there should no current.next.next==nil condition, if current.next.next==nil, then current.next will be the list.tail

Question on Exponential Search

Why do you add 1 to the boundValue here https://github.com/floyernick/Data-Structures-and-Algorithms/blob/master/ExponentialSearch/ExponentialSearch.go#L11 in the exponential search algorithm?

After trying a test case where I search for an element that is not in the data slice I get an error panic: runtime error: index out of range. I'm not sure why a +1 was added but when I remove it the problem goes away.

All of my code:

package main

import "fmt"

func exponential_search(data []int, key int) int {
  bound_value := 1
  for bound_value < len(data) && data[bound_value] < key {
    bound_value *= 2
  }
  if bound_value > len(data) {
    bound_value = len(data) - 1
  }
  return binary_search(data, bound_value, key)
}

func binary_search(data []int, bound int, key int) int {
  min := 0
  max := bound

  for min <= max {
    mid := int((max + min) / 2)
    if data[mid] == key {
      return mid
    } else if data[mid] < key {
      min = mid + 1
    } else if data[mid] > key {
      max = mid - 1
    }
  }
  return -1
}

func main() {
  data1 := []int{0,1,2,3,4,5,6,7,8,9}
  data2 := []int{}

  keys := []int{0,4,9,11,2,3,8,-1}

  for _, key := range keys {
    fmt.Println("Searching for", key)
    if index := exponential_search(data1, key); index != -1 {
      fmt.Println("Position:", index, "data:", data1[index])
    } else {
      fmt.Println("Key", key, "not found")
    }
  }
  // Search for an element in an empty slice.
  fmt.Println("Position:", exponential_search(data2, 11))
}

Output:

Searching for 0
Position: 0 data: 0
Searching for 4
Position: 4 data: 4
Searching for 9
Position: 9 data: 9
Searching for 11
Key 11 not found
Searching for 2
Position: 2 data: 2
Searching for 3
Position: 3 data: 3
Searching for 8
Position: 8 data: 8
Searching for -1
Key -1 not found
Position: -1

func RemoveByIndex in DoublyLinkedList.go has a problem

the block below has a problem that the previous head can still be referred to

if i == 0 {
	list.head.prev = nil
	list.head = list.head.next
	return true
}

it should be like this

if i == 0 {
	list.head = list.head.next
        list.head.prev = nil
	return true
}

The way to calculate the average in the BinarySearch may cause overflow.

In BinarySearch, there are a code may cause overflow.

int((maxIndex + minIndex) / 2)

If (maxIndex + minIndex) is greater than max int, there occurs overflow and return wrong number.
We should calcurate like below.

int(minIndex + (maxIndex-minIndex)/2)

I'll make a PR.

Flaky test

https://github.com/floyernick/Data-Structures-and-Algorithms/blob/6ae8c0f2e09c371f47f2a3c76f3b73989e4f3c45/BinarySearch/BinarySearch_test.go#L21

• This line could generate the number 0 in which case it would pass without making any verifications. suggest you add 10 to get some numbers.

another algorithm-go repo

Hi,
We can learn from each other :) link removed

Items in README.md should be linked

Data Structures and Algorithms

Clean and simple implementation in Go

Implementation

There are several data structures and algorithms implemented in this project. The list will be replenished with time.

Data structures

• Circular Buffer

Some Changes for MergeSort

#18
It Make MergeSort faster than before and I Commit a pull request.
————————————————————————————————————
Benchmark_MergeSort_new
Benchmark_MergeSort_new-12 10 101394033 ns/op 209956300 B/op 1000041 allocs/op
Benchmark_MergeSort_new-12 10 103156080 ns/op 209956320 B/op 1000041 allocs/op
Benchmark_MergeSort_new-12 10 105631558 ns/op 209956272 B/op 1000041 allocs/op
Benchmark_MergeSort_old
Benchmark_MergeSort_old-12 4 322263281 ns/op 582174710 B/op 4052123 allocs/op
Benchmark_MergeSort_old-12 3 333629871 ns/op 582175192 B/op 4052124 allocs/op
Benchmark_MergeSort_old-12 3 350259903 ns/op 582174706 B/op 4052122 allocs/op

Make repo go get-able by adding a .go file to top folder level

You need to make the top level of the repo a Go package in order to make it go get-able. Otherwise, it returns an error:

package github.com/floyernick/Data-Structures-and-Algorithms: no Go files in /Users/philip/src/github.com/floyernick/Data-Structures-and-Algorithms

It can as simple as a package declaration and it will work, i.e. in new file dsa.go at the top level of the package, just have a single line of package dsa and you're good to go.