算法列表
- 顺序查找（Sequential Search）
- 二叉树查找（Binary Search）
- 三叉树查找（Ternary Search）
- 插值查找（Interpolation Search）
- 斐波那契查找（Fibonacci Search）
- 指数查找（Exponential Search）
- 树表查找（Tree table lookup）
- 分块查找（Blocking Search）
- 哈希查找（Hash Search）
算法实现
顺序查找（Sequential Search）
funcSequentialSearch(array []int, targetint) int { ifarray==nil||len(array) ==0 { return-1 } fori :=0; i<len(array); i++ { ifarray[i] ==target { returni } } return-1}
二叉树查找（Binary Search）
基本二分查找
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}
三叉树查找（Ternary Search）
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}
插值查找（Interpolation Search）
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 } }
斐波那契查找（Fibonacci Search）
在是二分查找的一种提升算法，通过运用黄金比例的概念在数列中选择查找点进行查找，提高查找效率。注意同时属于一种有序查找算法
// 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}
指数查找（Exponential Search）
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 } }
树表查找（Tree table lookup）
分块查找（Blocking Search）
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}
