二分查找时间复杂度O(h)=O(log2n),具备非常高的效率,用R处理数据时有时候需要用到二分查找法以便快速定位
1 Rbisect <- function(lst, value){
2 low=1
3 high=length(lst)
4 mid=length(lst)%/%2
5 if (lst[low]==value) low
6 else if (lst[high]==value) high
7 else{
8 while (lst[mid] != value) {
9 if (value > lst[mid]){
10 low = mid+1
11 } else if (value < lst[mid]) {
12 high = mid - 1
13 }
14 if(high<low){
15 mid=-1;break
16 }
17 mid=(low+high)%/%2
18 }
19 mid
20 }
21 }