Golang Binary search

I'm practicing an interview algorithm, now coding it in Go. The purpose is to practice basic interview algorithms, and my skills in Go. I'm trying to perform a Binary search of an array of numbers.

package main

import "fmt"

func main() {
	searchField := []int{2, 5, 8, 12, 16, 23, 38, 56, 72, 91}
	searchNumber := 23

    fmt.Println("Running Program")
    fmt.Println("Searching list of numbers: ", searchField)
    fmt.Println("Searching for number: ", searchNumber)

    numFound := false
    //searchCount not working. Belongs in second returned field
    result, _ := binarySearch2(searchField, len(searchField), searchNumber, numFound)
    fmt.Println("Found! Your number is found in position: ", result)
    //fmt.Println("Your search required ", searchCount, " cycles with the Binary method.")
}

func binarySearch2(a []int, field int, search int, numFound bool) (result int, searchCount int) {
	//searchCount removed for now.
	searchCount, i := 0, 0
	for !numFound {
		searchCount++
		mid := i + (field-i)/2
		if search == a[mid] {
			numFound = true
			result = mid
			return result, searchCount
		} else if search > a[mid] {
			field++
			//i = mid + 1 causes a stack overflow
			return binarySearch2(a, field, search, numFound)
		}
		field = mid
		return binarySearch2(a, field, search, numFound)
	}
	return result, searchCount
}

The main problems I'm coming across are:

1. When the number is higher in the list than my mid search, am I truly continuing a binary search, or has it turned to a sequential? How can I fix that? The other option I've placed has been commented out because it causes a stack overflow.

2. I wanted to add a step count to see how many steps it takes to finish the search. Something to use with other search methods as well. If I print out the search count as is, it always reads one. Is that because I need to return it (and therefore call for it in the header) in the method?

I understand Go has methods that streamline this process. I'm trying to increase my knowledge and coding skills. I appreciate your input.

You're not doing a binary search properly. First off, your for loop is useless, since each branch in the conditional tree has a return statement in it, so it can never run more than one iteration. It looks like you started to code it iteratively, then swapped to a recursive setup, but only kinda halfway converted it.

The idea of a binary search is that you have a high and low index and search the midway point between them. You're not doing that, you're just incrementing the field variable and trying again (which will cause you to search each index twice until you find the item or segfault by running past the end of the list). In Go, though, you don't need to keep track of the high and low indexes, as you can simply subslice the search field as appropriate.

Here's a more elegant recursive version:

func binarySearch(a []int, search int) (result int, searchCount int) {
	mid := len(a) / 2
	switch {
	case len(a) == 0:
		result = -1 // not found
	case a[mid] > search:
		result, searchCount = binarySearch(a[:mid], search)
	case a[mid] < search:
		result, searchCount = binarySearch(a[mid+1:], search)
		if result >= 0 { // if anything but the -1 "not found" result
			result += mid + 1
		}
	default: // a[mid] == search
		result = mid // found
	}
	searchCount++
	return
}

https://play.golang.org/p/UyZ3-14VGB9

func BinarySearch(a []int, x int) int {
    r := -1 // not found
    start := 0
    end := len(a) - 1
    for start <= end {
        mid := (start + end) / 2
        if a[mid] == x {
            r = mid // found
            break
        } else if a[mid] < x {
            start = mid + 1
        } else if a[mid] > x {
            end = mid - 1
        }
    }
    return r
}

Off-topic, but might help others looking for a simple binary search who could land here.

There's a generic binary search module on github since the standard library doesn't offer this common functionality: https://github.com/bbp-brieuc/binarysearch

func BinarySearch(array []int, target int) int {
  startIndex := 0
  endIndex := len(array) - 1
  midIndex := len(array) / 2
  for startIndex <= endIndex {

	value := array[midIndex]

	if value == target {
		return midIndex
	}

	if value > target {
		endIndex = midIndex - 1
		midIndex = (startIndex + endIndex) / 2
		continue
	}

	startIndex = midIndex + 1
	midIndex = (startIndex + endIndex) / 2
}

  return -1
}

generic type version ! (go 1.18)

Time Complexity : log2(n)+1

package main
import "golang.org/x/exp/constraints"

func BinarySearch[T constraints.Ordered](a []T, x T) int {
  	start, mid, end := 0, 0, len(a)-1
   	for start <= end {
   		mid = (start + end) >> 1
   		switch {
   		case a[mid] > x:
   			end = mid - 1
   		case a[mid] < x:
   			start = mid + 1
   		default:
   			return mid
   		}
   	}
   	return -1
}

full version with iteration counter at playground.