the following function will find a single element in list of pairs, expose binary search and naive linear search

find_single_int_in_pairs.go

// Interpolation Search in Golang
package main

import (
	"fmt"
	"math"
)

var (
	index      int
	indexTuple []int64
)

// SearchDuplicatesByIndexMatch uses liniar naive search by the iterative model over an array of integers
// to find a single number in a list of pairs.
// the model will copy the original array).
// return: the single int (int)
// expects: sorted array.
func SearchDuplicatesByIndexMatch(a []int64) int64 {
	//TODO: reduce allocation.
	n := len(a)
	index = 0
	if n > 2 {
		indexTuple = a[:2]
	}
	for index < n {
		if indexTuple[0] != indexTuple[1] {
			if index+1 == n-1 { // check for last index
				return indexTuple[1]
			}
			return indexTuple[0] // always return the fist index, which is even number.
		}
		if index+3 == n { // check for last two
			index++
			indexTuple = a[index:] // get new tuple.
		} else {
			index = index + 2               // move on to the next tuple.
			indexTuple = a[index : index+2] // get new tuple.
		}
	}
	return -1
}

// BinarySearchDuplicates uses a binary search by the iterative model over an array of integers
// to find a single number in a list of pairs.
// the algorithm used an iterator and not a recursive.
// the model will move the index instead of copies (of the original array).
// The logic is scane a given noneven list, divide it, make sure we've no overlaps between slice A false
// eventually the unique number will always be in the noneven list.
// return: the single int (int)
// expects: sorted array.
func BinarySearchDuplicates(nonEvenSlice []int64) int64 {
	n := len(nonEvenSlice)
	left, mid, right := 0, 0, n
	// do binary search for at least 3 items.
	for n > 3 {
		mid = right - int(math.Round(float64(n)/2))
		if nonEvenSlice[mid-1] == nonEvenSlice[mid] {
			// pop items when overlaps, between two slices i.e slice1[x] slice2[x+1]
			mid, right = (mid + 1), (right)
			left, right, n = getNonEvenBoundries(left, mid, right)
		} else {
			left, right, n = getNonEvenBoundries(left, mid, right)
		}
	}

	return compareLastTree(nonEvenSlice[left:right])
}

// compareLastTree will analyse an array of 3 ints and retrive the uniq one.
// the followign method expects for a slice within 3 items 2 duplicates and 1
// uniq.
func compareLastTree(nonEvenSlice []int64) (res int64) {
	if len(nonEvenSlice) < 3 {
		//TODO: error handling
		res = -1
	}

	if nonEvenSlice[0] == nonEvenSlice[1] && nonEvenSlice[1] != nonEvenSlice[2] {
		res = nonEvenSlice[2]
	}
	if nonEvenSlice[0] != nonEvenSlice[1] && nonEvenSlice[1] == nonEvenSlice[2] {
		res = nonEvenSlice[0]
	}

	return res
}

// getNonEvenBoundries retrive size of a, b and compute new boundires.
func getNonEvenBoundries(left, mid, right int) (l, r, n int) {
	series1, series2 := (mid - left), (right - mid)
	if series1%2 != 0 {
		if series1 < 0 {
			l, r, n = mid, right, 0
		}
		l, r, n = left, mid, series1
	}
	if series2%2 != 0 {
		l, r, n = mid, right, series2
	}
	return l, r, n
}

func main() {
	items := []int64{}
	// tests #1 - uniq first
	items = []int64{1, 2, 2}
	fmt.Println("uniq first:", BinarySearchDuplicates(items))

	// tests #2 - uniq last
	items = []int64{1, 1, 3}
	fmt.Println("uniq last:", BinarySearchDuplicates(items))
	//
	// tests #2 - uniq in middle
	items = []int64{1, 1, 5, 5, 6, 7, 7, 8, 8, 9, 9}
	fmt.Println("uniq in middle:", BinarySearchDuplicates(items))

	// tests #3 - worst case, uniq last in big list.
	items = make([]int64, 0, 199)
	var i int64
	for i = 0; i <= 198; i++ {
		items = append(items, i, i)
	}
	items = append(items, 199)
	fmt.Println("uniq in large set:", BinarySearchDuplicates(items))
	fmt.Println("uniq in large set:", SearchDuplicatesByIndexMatch(items))
}