golang数据结构和算法之BinarySearch二分查找法

时间:2022-09-24 15:06:06

基础语法差不多了,

就需要系统的撸一下数据结构和算法了。

没找到合适的书,

就参考github项目:

https://github.com/floyernick/Data-Structures-and-Algorithms/

注意golang里没有main函数,不能执行,

测试时,使用go test即可。

BinarySearch.go

package BinarySearch

//二分法查找
func BinarySearch(array []int, number int) int {
	minIndex := 0
	maxIndex := len(array) - 1
	for minIndex <= maxIndex {
		midIndex := int((maxIndex + minIndex) / 2)
		midItem := array[midIndex]
		if number == midItem {
			return midIndex
		}

		if midItem < number {
			minIndex = midIndex + 1
		} else if midItem > number {
			maxIndex = midIndex - 1
		}
	}

	return -1
}

  

BinarySearch_test.go

package BinarySearch

import (
	"fmt"
	"math/rand"
	"testing"
	"time"
)

//先排序
func SortArray(array []int) {
	for itemIndex, itemValue := range array {
		for itemIndex != 0 && array[itemIndex-1] > itemValue {
			array[itemIndex] = array[itemIndex-1]
			itemIndex -= 1
		}
		array[itemIndex] = itemValue
	}
}

func TestBinarySearch(t *testing.T) {
	random := rand.New(rand.NewSource(time.Now().UnixNano()))
	fmt.Println(random)
	array := make([]int, random.Intn(100))
	fmt.Println(array)

	for i := range array {
		array[i] = random.Intn(100)
	}
	fmt.Println(array)
	SortArray(array)
	fmt.Println(array)

	for _, value := range array {
		result := BinarySearch(array, value)
		if result == -1 {
			t.Fail()
		}
	}
}

  

golang数据结构和算法之BinarySearch二分查找法

golang数据结构和算法之BinarySearch二分查找法