二分法查找-算法学习

二分法查找

二分搜索算法

在计算机科学中,二分搜索(英语:binary search),也称折半搜索(英语:half-interval search)[1]、对数搜索(英语:logarithmic search)[2],是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜索过程结束;如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空,则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。

具体实现

GitHub版本库的二分法查找。

算法实现

该算法非常快,从已经排序好的数组查找制定的元素。
1. 初始化,分别有两个指向开始的元素和结束的元素。
2. 每次循环后,去掉一半的元素,同时更新对应的开始和结束的指向。
3. 循环结束的条件是开始小于等于结束(默认元素是升序排列)

耗时分析

机器配置 ThinkPad T440s CPU i5-4300U Memory 8GB
num 1000 search 2992889 cost time is 4.0531158447266E-6 s
num 10000 search 2207856 cost time is 5.9604644775391E-6 s
num 100000 search 1142758 cost time is 8.1062316894531E-6 s

算法分析

最坏时间复杂度 O(log n)}
最优时间复杂度 O(1)}
平均时间复杂度 O(log n)}
空间复杂度 迭代: O(1)}
递归: O(log n)}
(无尾调用消除)

参考链接

  1. 二分法查找
  2. 二分法查找
  3. 二分法查找 百度百科

Gin和grpc搭建-学习Go语言

安装grpc

如果你遇到这样的错误

package google.golang.org/grpc: unrecognized import path "google.golang.org/grpc"(https fetch: Get https://google.golang.org/grpc?go-get=1: dial tcp 216.239.37.1:443: i/o timeout)

解决方案,采用最新github的地址。

git clone https://github.com/grpc/grpc-go.git $GOPATH/src/google.golang.org/grpc
git clone https://github.com/golang/net.git $GOPATH/src/golang.org/x/net
git clone https://github.com/golang/text.git $GOPATH/src/golang.org/x/text
go get -u github.com/golang/protobuf/{proto,protoc-gen-go}
git clone https://github.com/google/go-genproto.git $GOPATH/src/google.golang.org/genproto

cd $GOPATH/src/
go install google.golang.org/grpc

继续报错:

google.golang.org/grpc/internal/channelz/types_linux.go:26:2: cannot find package "golang.org/x/sys/unix" in any of:
    /usr/local/go/src/golang.org/x/sys/unix (from $GOROOT)
    /go/src/golang.org/x/sys/unix (from $GOPATH)

解决方案,依然采用github的地址。

git clone https://github.com/golang/sys.git $GOPATH/src/golang.org/x/sys

gin框架

如果你想执行gin的example的例子。

go run grpc/server.go
grpc/server.go:7:2: cannot find package "github.com/gin-gonic/gin/examples/grpc/pb" in any of:
    /usr/local/go/src/github.com/gin-gonic/gin/examples/grpc/pb (from $GOROOT)
    /go/src/github.com/gin-gonic/gin/examples/grpc/pb (from $GOPATH)

解决方案,拉取gin的包。

go get -u github.com/gin-gonic/gin

参考链接

  1. golang安装gRpc

单元测试-学习Go语言

实现

采用自身的testing包实现。

踩坑

单元测试和源文件必要放在同一个目录下,才可以正常执行。

Go PHPUnit
*_test文件和源文件一起 必须 任意
断言 第三方库 支持
mock 支持 支持

语法

执行单元测试

go test -v -cover=true ./src/rpc/client_test.go ./src/rpc/client.go

简单的断言

/*
* @Author: GeekWho
* @Date:   2018-07-20 11:33:43
* @Last Modified by:   GeekWho
* @Last Modified time: 2018-07-20 12:29:33
*/
package rpc

import (
    "testing"

    "github.com/stretchr/testify/assert"
)

func TestRun(t *testing.T) {
    assert.Equal(t, "rpc", "rpc")
}