SortedStrArray.go

import (
	"strings"
)

type SortedStrArray []string

func NewSortedStrArray(arr []string) (*SortedStrArray) {
	res := SortedStrArray(arr)
	return &res
}

func (this *SortedStrArray) Add(newValue string) (int) {
	_, i := this.Find(newValue)
	this.insert(i, newValue)
	return len(*this)
}

func (this *SortedStrArray) insert(i int, newValue string) (int) {
	arr := []string(*this)
	arrLen := len(arr)
	
	if arrLen == 0 {
		arr = append(arr, newValue)
	} else {
		arr = append(arr, "")
		copy(arr[i+1:], arr[i:])
		arr[i] = newValue
	}
	*this = arr
	return arrLen + 1
}

func (this *SortedStrArray) Find(newValue string) (string, int) {
	arr := []string(*this)
	lcv := strings.ToLower(newValue)
	
	arrLen := len(arr)
	l := 0
	r := arrLen
	var i int
	var v string
	
	for true {
		i = l + (r - l) / 2
		if r == 0 {
			return "", 0
		} else if i >= arrLen {
			return "", i
		}
		v = strings.ToLower(arr[i])
		if v == lcv {
			return arr[i], i
		} else if r - l == 0 {
			return "", l
		} else if v > lcv {
			if r - l == 1 {
				return "", l
			}
			r = i
		} else if v < lcv {
			if r - l == 1 {
				return "", r
			}
			l = i
		} else {
			panic("Impossible")
		}
	}
	return "", -1
}