CODEWITHSUNDEEP
gobinary-search
as.beaulieu
as.beaulieu

Reputation: 484

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.

Upvotes: 3

Views: 22956

Answers (5)

Vivian K. Scott
Vivian K. Scott

Reputation: 892

for GO 1.21

slices.BinarySearch is bundled in Go packages.

package main
import (
    "fmt"
    "slices"
)
func main() {
    searchField := []int{2, 5, 8, 12, 16, 23, 38, 56, 72, 91}
    fmt.Println( slices.BinarySearch(searchField, 5) )
}

It's generic also.

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.

Upvotes: 3

binary searcher
binary searcher

Reputation: 31

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

Upvotes: 2

blues911
blues911

Reputation: 910

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
}

Upvotes: 8

Kaedys
Kaedys

Reputation: 10138

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

Upvotes: 13

Michael Horojanski
Michael Horojanski

Reputation: 4701

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
}

Upvotes: 1

Related Questions