Random choose a city, the more population it has, the more possibly it may be choosed.

searchcity.go

package main

import (
	"math/rand"
	"time"
)

type SearchError struct {
	Reason string
}

func (this *SearchError) Error() string {
	return this.Reason
}

func BinarySearchInner(rangeList []int, start, end, target int) (result int, err error) {
	if start > end {
		return -1, &SearchError{"bad binary search"}
	}
	if start+1 == end {
		return start, nil
	}
	pos := (end-start)/2 + start
	if target > rangeList[pos] {
		return BinarySearchInner(rangeList, pos, end, target)
	} else {
		return BinarySearchInner(rangeList, start, pos, target)
	}
}

func BinarySearch(rangeList []int, target int) (result int, err error) {
	listLen := len(rangeList)
	if listLen == 0 || listLen == 1 || target >= rangeList[listLen-1] {
		return -1, &SearchError{"bad array argument"}
	}
	if listLen == 2 {
		return 0, nil
	}
	start, end := 0, listLen-1
	return BinarySearchInner(rangeList, start, end, target)
}

func SearchCity(cities map[string]int) (result string, err error) {
	if len(cities) == 0 {
		return "", &SearchError{"no city"}
	}
	rangeList := make([]int, len(cities)+1)
	cityList := make([]string, len(cities)+1)
	last, index := 0, 0
	for name, population := range cities {
		cityList[index] = name
		last += population
		rangeList[index+1] = last
		index += 1
	}
	target := rand.New(rand.NewSource(time.Now().UnixNano())).Intn(last)
	pos, err := BinarySearch(rangeList, target)
	if err == nil {
		return cityList[pos], nil
	} else {
		return "", err
	}
}

func main() {

}

searchcity_test.go

package main

import (
	"testing"
)

func TestBinarySearch(t *testing.T) {
	value1, _ := BinarySearch([]int{}, 100)
	if value1 != -1 {
		t.Error("search empty list _or")
	}

	value2, _ := BinarySearch([]int{1}, 100)
	if value2 != -1 {
		t.Error("search list with 1 element _or")
	}

	value3, _ := BinarySearch([]int{0, 100}, 101)
	if value3 != -1 {
		t.Error("search out of range _or")
	}

	value4, _ := BinarySearch([]int{0, 100}, 50)
	if value4 != 0 {
		t.Error("search list with 2 elements _or")
	}

	value5, _ := BinarySearch([]int{0, 100, 1000}, 50)
	if value5 != 0 {
		t.Error("search in first part _or")
	}

	value6, _ := BinarySearch([]int{0, 100, 1000}, 500)
	if value6 != 1 {
		t.Error("search in second part _or")
	}

	value7, _ := BinarySearch([]int{0, 100, 700, 1000}, 50)
	if value7 != 0 {
		t.Error("search in first part with 4 elements _or")
	}

	value8, _ := BinarySearch([]int{0, 100, 700, 1000}, 300)
	if value8 != 1 {
		t.Error("search in second part with 4 elements _or")
	}

	value9, _ := BinarySearch([]int{0, 100, 700, 1000}, 800)
	if value9 != 2 {
		t.Error("search in third part with 4 elements _or")
	}
}

func TestSearchCity(t *testing.T) {
	cities := map[string]int{}
	city, err := SearchCity(cities)
	if err == nil {
		t.Error("seach empty city without error")
	}

	count := 10000
	choosedCity := make([]string, count)
	cities = map[string]int{
		"shanghai": 10000,
	}
	for i := 0; i < count; i++ {
		city, err = SearchCity(cities)
		if err != nil {
			t.Error("search error")
			panic(err)
		}
		choosedCity[i] = city
	}

	for i := 0; i < count; i++ {
		if choosedCity[i] != "shanghai" {
			t.Error("choose error with one city")
			break
		}
	}

	// I can only test this by using statistics
	cities = map[string]int{
		"shanghai": 10000,
		"sg":       100,
		"LA":       1000,
	}
	citiesCount := map[string]int{
		"shanghai": 0,
		"sg":       0,
		"LA":       0,
	}
	count = 100000
	for i := 0; i < count; i++ {
		city, err = SearchCity(cities)
		if err != nil {
			t.Error("choose error")
			break
		}
		citiesCount[city] += 1
	}
	if citiesCount["shanghai"] < citiesCount["LA"] || citiesCount["LA"] < citiesCount["sg"] {
		t.Error("choose error with probability")
	}
}