Question on Exponential Search

[mrmcmuffinz]

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