搜索算法实现 - Golang版

funcSequentialSearch(array []int, targetint) int {
ifarray==nil||len(array) ==0 {
return-1    }
fori :=0; i<len(array); i++ {
ifarray[i] ==target {
returni        }
    }
return-1}

funcBinarySearch(array []int, targetint) int {
ifarray==nil||len(array) ==0 {
return-1    }
low :=0high :=len(array) -1mid :=0forlow<=high {
//mid = low + (high-low)/2mid=low+ (high-low)>>1ifarray[mid] >target {
high=mid-1        } elseifarray[mid] <target {
low=mid+1        } else {
returnmid        }
    }
return-1}

funcLowerBound(array []int, targetint) int {
low, high, mid :=0, len(array)-1, 0forlow<=high {
//mid = low + (high-low)/2mid=low+ (high-low)>>1ifarray[mid] >=target {
high=mid-1        } else {
low=mid+1        }
    }
returnlow}

funcUpperBound(array []int, targetint) int {
low, high, mid :=0, len(array)-1, 0forlow<=high {
//mid = low + (high-low)/2mid=low+ (high-low)>>1ifarray[mid] >target {
high=mid-1        } else {
low=mid+1        }
    }
returnlow}

funcTernarySearch(array []int, targetint) int {
ifarray==nil||len(array) ==0 {
return-1    }
low, high :=0, len(array)-2mid1, mid2 :=0, 0forlow<=high {
mid1=low+ (high-low)/3mid2=high+ (high-low)/3ifarray[mid1] ==target {
returnmid1        } elseifarray[mid2] ==target {
returnmid2        }
iftarget<array[mid1] {
high=mid1-1        } elseiftarget>array[mid2] {
low=mid2+1        } else {
low=mid1+1high=mid2-1        }
    }
return-1}

funcInterpolationSearch(array []int, targetint) int {
ifarray==nil||len(array) ==0 {
return-1    }
low, high :=0, len(array)-1varmid=0forarray[low] <target&&array[high] >target {
//mid = low + (high-low)/2mid=low+ (high-low)>>1ifarray[mid] <target {
low=mid+1        } elseifarray[mid] >target {
high=mid-1        } else {
returnmid        }
    }
ifarray[low] ==target {
returnlow    } elseifarray[high] ==target {
returnhigh    } else {
return-1    }
}

// FibonacciSearch 斐波那查找funcFibonacciSearch(array []int, targetint) int {
ifarray==nil||len(array) ==0 {
return-1    }
high :=len(array) -1max :=array[high]
fibMMm2 :=0// (m-2)'th Fibonacci No.fibMMm1 :=1// (m-1)'th Fibonacci No.fibM :=fibMMm2+fibMMm1// m'th FibonacciforfibM<max {
fibMMm2=fibMMm1fibMMm1=fibMfibM=fibMMm2+fibMMm1    }
varmid, offset=0, -1forfibM>1 {
mid=algorithm.Min(offset+fibMMm2, high)
ifarray[mid] <target {
fibM=fibMMm1fibMMm1=fibMMm2fibMMm2=fibM-fibMMm1offset=mid        } elseifarray[mid] >target {
fibM=fibMMm2fibMMm1=fibMMm1-fibMMm2fibMMm2=fibM-fibMMm1        } else {
returnmid        }
    }
ifoffset<high&& (array[offset+1] ==target) {
returnoffset+1    }
return-1}
// fibonacciRecursion 递归求斐波那数// f(n) = f(n-1) + f(n-2), n >= 2funcfibonacciRecursion(nint) int {
ifn==0 {
return0    } elseifn==1 {
return1    }
returnfibonacciRecursion(n-1) +fibonacciRecursion(n-2)
}
// fibonacci 求斐波那数funcfibonacci(nint) int {
a :=0b :=1fori :=0; i<n; i++ {
temp :=aa=bb=temp+a    }
returna}

funcExponentialSearch(array []int, targetint) int {
ifarray==nil||len(array) ==0 {
return-1    }
ifarray[0] ==target {
return0    }
length :=len(array)
ifarray[length-1] ==target {
returnlength-1    }
searchRange :=1forsearchRange<length&&array[searchRange] <=target {
//searchRange = searchRange * 2searchRange=searchRange<<1    }
//startIndex := searchRange / 2startIndex :=searchRange>>1endIndex :=algorithm.Min(searchRange, length)
bi :=BinarySearch(array[startIndex:endIndex], target)
ifbi==-1 {
return-1    } else {
returnbi+startIndex    }
}

funcJumpSearch(array []int, targetint) int {
ifarray==nil||len(array) ==0 {
return-1    }
length :=len(array)
step :=int(math.Sqrt(float64(length)))
prev :=0forarray[algorithm.Min(step, length)-1] <target {
prev=stepstep+=int(math.Sqrt(float64(length)))
ifprev>=length {
return-1        }
    }
forarray[prev] <target {
prev++ifprev==algorithm.Min(step, length) {
return-1        }
    }
ifarray[prev] ==target {
returnprev    }
return-1}