binary search in go

binarySearch.go

// Expected input: a sorted array
// Return: index n, such that array[n] <= target < array[n+1]
func binarySearch(array []uint64, target uint64) (int, error) {
	var lower, upper = 0, len(array) - 1
	var preLower, preUpper = 0, len(array) - 1

	for array[lower] > target || array[lower+1] <= target {
		if array[lower+1] == target {
			return lower + 1, nil
		}
		midpoint := (lower + upper) / 2
		if array[midpoint] < target {
			lower = midpoint
		} else {
			upper = midpoint
		}

		// Error handling
		if lower == preLower && upper == preUpper {
			return lower, errors.New("Unable to find target")
		}
		preLower = lower
		preUpper = upper
	}

	return lower, nil
}