Binary Search

This code snippet searches for a value in a sorted slice/array in O(log n) using the binary search algorithm.

Code

{{/*
	Searches a sorted slice/array in O(log n) time using binary search.
	See <https://yagpdb-cc.github.io/code-snippets/binary-search> for more information.

	Author: Alikuxac <https://github.com/alikuxac>
*/}}

{{define "binary_search"}}
	{{- $list := .List}}
	{{- $left := or .Left 0}}
	{{- $right := or .Right (sub (len $list) 1)}}
	{{- $value := .Value}}
	{{- if .Found}}
		{{- if ge $right 1}}
			{{- $mid := (div (add $left $right) 2) | toInt}}
			{{- if eq (index $list $mid) $value}}
				{{- .Set "Result" $mid}}
				{{- .Set "Found" false}}
			{{- end}}
			{{- if gt (index $list $mid) $value}}
				{{- .Set "Right" (sub $mid 1)}}
				{{- template "binary_search" .}}
			{{- else}}
				{{- .Set "Left" (add $mid 1)}}
				{{- template "binary_search" .}}
			{{- end}}
		{{- else}}
			{{- .Set "Result" -1}}
			{{- .Set "Found" false}}
		{{- end}}
	{{- end -}}
{{end}}

Usage

First, copy the above snippet to the top of your code.
To use it, you will need to construct a map holding your input slice/array in addition to the value you wish to search for:

{{/* code snippet here */}}
{{$query := sdict "List" (cslice 1 2 3 5 7 8) "Value" 2 "Found" true}}

note

"Found" true tells the template to begin searching in the slice/array, so make sure to set it!

Then, we can run the template, passing the query as data:

{{/* code snippet here */}}
{{$query := sdict "List" (cslice 1 2 3 5 7 8) "Value" 2 "Found" true}}
{{template "binary_search" $query}}

Running the template will add a new value to your map, Result, which is the index where the element was found, or -1 if it wasn't found. We can access it using dot notation or index, like such:

{{/* code snippet here */}}
{{$query := sdict "List" (cslice 1 2 3 5 7 8) "Value" 2 "Found" true}}
{{template "binary_search" $query}}
Index: {{$query.Result}}

Author

This code snippet was written by @alikuxac.