首先放今天的力扣打卡題，
在第一次做的程序中，我忽略了“升序排列”這個條件，沒有使用二分，
由于是最近才剛開始學golang，所以很有興趣的在這道題里使用了go的大殺器——goroutine，思路就是使用兩個goroutine，一個從頭到尾遍歷陣列，找出開始位置，一個倒序遍歷陣列，找到結束位置，
代碼如下：
func searchRange(nums []int, target int) []int {
//使用WaitGroup控制goroutine
var wg sync.WaitGroup
//wg加入兩個任務
wg.Add(2)
length := len(nums)
//將start end直接賦值-1 當找不到時直接回傳
start := -1
end := -1
//第一個goroutine
go func() {
//函式運行結束后wg任務-1
defer wg.Done()
//正序遍歷陣列，找到start就跳出
for i := 0; i < length; i++ {
if nums[i] == target {
start = i
break
}
}
}()
go func() {
defer wg.Done()
//倒序遍歷陣列，找到end就跳出
for i := length-1; i >= 0; i-- {
if nums[i] == target {
end = i
break
}
}
}()
//wg一直等待兩個任務結束
wg.Wait()
return []int{start,end}
}
由于go出色的性能，結果還是挺令人滿意，
在完成這道題后，我去看了看題解，這才發現陣列是有序的，可以使用二分法完成，
而官方的Go題解非常簡練優雅，
這里放上代碼并加上注釋，
func searchRange(nums []int, target int) []int {
/*
SearchInts函式會回傳陣列中target第一次出現的位置，
如果沒有找到，則會回傳陣列長度n，
*/
//找起始位置
leftmost := sort.SearchInts(nums, target)
if leftmost == len(nums) || nums[leftmost] != target {
return []int{-1, -1}
}
//結束位置（這里是找target+1，比target大一的數字的起始位置就在target結束位置的右邊）
rightmost := sort.SearchInts(nums, target + 1) - 1
return []int{leftmost, rightmost}
}
其中使用到了SearchInts這個函式，
跟蹤進去，發現它呼叫了sort包下的Search函式，
這里對這個使用二分進行查找的函式進行分析，
func Search(n int, f func(int) bool) int {
i, j := 0, n
for i < j {
/*
這里使用了移位操作，其結果與(i+j)/2一樣，
uint是無符號的int，范圍是2^32即0到4294967295，使用uint可以避免因為i+j太大而造成的溢位
*/
h := int(uint(i+j) >> 1)
// 如果f(h)回傳false，說明從i到h中沒有目標值，這時更新i為h+1 從原先的i到現在的i之間的數就不會再次掃描了
//相反的，如果f(h)回傳true，說明從i到h中有目標值，這時更新j為 h
if !f(h) {
i = h + 1
} else {
j = h // preserves f(j) == true
}
}
//當 i==j 時，說明找到了（或者找完了但是沒有找到，這時回傳的是陣列長度）
return i
}
在閱讀這段簡單的原始碼時，其中的移位操作很有趣，在此之前，我并不知道還可以使用移位來進行/2的操作，其中原理也很簡單：
在二進制中，每一位等于前面所有位的值之和再加一，
例如，7位二進制的最大值為1111111，即127，
給它加一即為10000000,128，
因此，對數字向右移位一位，就是其/2的結果，
而在查資料的時候，發現移位實作的乘除法比直接乘除的效率高很多，
總結：
1.遇到查找有序陣列中的元素的時候應該反應出來使用二分，
2.遇到需要大量進行乘除法的操作時，考慮使用移位，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/229312.html
標籤：其他