Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

sort: Search function is not exactly the way binary search should be. #37869

Closed
solodynamo opened this issue Mar 15, 2020 · 3 comments
Closed

sort: Search function is not exactly the way binary search should be. #37869

solodynamo opened this issue Mar 15, 2020 · 3 comments

Comments

@solodynamo
Copy link

@solodynamo solodynamo commented Mar 15, 2020

What version of Go are you using (go version)?

1.13/1.14

Does this issue reproduce with the latest release?

Yes

What operating system and processor architecture are you using (go env)?

GO111MODULE=""
GOARCH="amd64"
GOBIN=""
GOCACHE="/home/runner/.cache/go-build"
GOENV="/config/go/env"
GOEXE=""
GOFLAGS=""
GOHOSTARCH="amd64"
GOHOSTOS="linux"
GOINSECURE=""
GONOPROXY=""
GONOSUMDB=""
GOOS="linux"
GOPATH="/home/runner/go"
GOPRIVATE=""
GOPROXY="https://proxy.golang.org,direct"
GOROOT="/usr/lib/go-1.14"
GOSUMDB="sum.golang.org"
GOTMPDIR=""
GOTOOLDIR="/usr/lib/go-1.14/pkg/tool/linux_amd64"
GCCGO="gccgo"
AR="ar"
CC="gcc"
CXX="g++"
CGO_ENABLED="1"
GOMOD="/home/runner/UntimelySerpentineDivisor/go.mod"
CGO_CFLAGS="-g -O2"
CGO_CPPFLAGS=""
CGO_CXXFLAGS="-g -O2"
CGO_FFLAGS="-g -O2"
CGO_LDFLAGS="-g -O2"
PKG_CONFIG="pkg-config"
GOGCCFLAGS="-fPIC -m64 -pthread -fmessage-length=0 -fdebug-prefix-map=/tmp/go-build487742067=/tmp/go-build -gno-record-gcc-switches

What did you do?

So, the comment over here says what a standard binary search should do.

Now look through this code
Above I am trying to find which two elements from the array add to the target. Ex : if 9 then 2 and 7 i.e indexes 0 and 1.
Run go test -v and see the quirk.

What did you expect to see?

As per the search function comment, my search code looks like this:
ii := sort.Search(len(ak), func(i int) bool { return ak[i] == targ })
Above I wish to search If the array contains an element or not. So I sorted the array(ASC) and started searching for targ

Dry Run:

input : []int{2, 7, 11, 15}

target: 7

// library code
func Search(n int, f func(int) bool) int {
	i, j := 0, n
	for i < j {
		h := int(uint(i+j) >> 1) // avoid overflow when computing h
		if !f(h) {
			i = h + 1 // preserves f(i-1) == false
		} else {
			j = h // preserves f(j) == true
		}
	}
	return i
}
  • i = 0 and j = 4 -> h = 2, input[2] = 11 (as per code is arr[2] == 7?..no) so the code increases the index and goes forward! .. I expected it will internally will go back and eventually find where 7 lies.

What did you see instead?

I saw that in code, the index position is incremented instead of decrement.
I think this is not how a standard binary search works.. Ideally if it finds current number is larger than target just go back(as the array is sorted in ascending order) but in this case it goes forward and that's why it would never find 7.

Possible Solution: If I change my search closure function to this
sort.Search(len(ak), func(i int) bool { return ak[i] >= targ })
Then It works fine but that solution comes after you keep aside your binary search logic you read in algorithms books and peek into the code and understand what's happening inside. I feel either correct the comment or the code.

There is a possibility that I might have missed something, please help in that case. Thanks!

@randall77
Copy link
Contributor

@randall77 randall77 commented Mar 15, 2020

Binary search is never going to work when the function you pass uses ==. The searcher has no way of knowing, when the element doesn't match, whether it should recurse to smaller indexes or larger ones.

sort.Search has no idea that you're sorting integers, or even which sort direction was used. It has no way of knowing "which way is up", except from the results of your comparison function.

I agree that sort.Search isn't the easiest thing to use. But there's nothing wrong with it, it does what it is specified to do. We can't change its behavior now.

You might want to consult https://github.com/golang/go/wiki/Questions for places to ask about this if you're still confused.

@randall77 randall77 closed this Mar 15, 2020
@solodynamo
Copy link
Author

@solodynamo solodynamo commented Mar 16, 2020

@randall77 this conflicts with the very first thing you said above. The comment should be altered considering devs think binary search the way it is usually described in books before actually seeing the code which works fine.

@randall77
Copy link
Contributor

@randall77 randall77 commented Mar 16, 2020

I don't understand why you think that conflicts.
The caller has to check whether data[i] == 23, not the function passed in. As in:

sort.Search(n, func(i int) bool { return data[i] >= 23 } )
if data[i] == 23 { ... }
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
2 participants
You can’t perform that action at this time.