有些繁琐的递归实现
#include <stdio.h> #include <limits.h> //binary search, find first value == v element's index //lt < , le <= , eq =, ne != , ge >=, gt > int bin_s_first_eq(int* a, int l, int r, int v,int maxLtIndex, int minEqIndex){ if(r<l) return -1; int m = l+((r-l)>>1); printf("a[m] a[%d]=%d ,maxLtI:%d,minEqI:%d ",m,a[m],maxLtIndex, minEqIndex); if(a[m] < v){ maxLtIndex = maxLtIndex < m ? m : maxLtIndex; if(minEqIndex - maxLtIndex == 1){ printf("find min:%d max:%d ",minEqIndex, maxLtIndex); return minEqIndex; }else{ //go right printf("go right "); return bin_s_first_eq(a,m+1,r,v,maxLtIndex, minEqIndex); } }else if(a[m] > v){ //go left printf("go left "); return bin_s_first_eq(a,l,m-1,v,maxLtIndex, minEqIndex); }else{//eq minEqIndex = minEqIndex > m ? m : minEqIndex; if(minEqIndex - maxLtIndex == 1 || minEqIndex == 0){ printf("find min:%d max:%d ",minEqIndex, maxLtIndex); return minEqIndex; }else{ //go left printf("go left "); return bin_s_first_eq(a,l,m-1,v,maxLtIndex, minEqIndex); } } } int bin_s_first_eq2(int* a,int n,int v){ int l = 0; int h = n-1; int m; while(l<=h){ m = l+((h-l)>>1); if(a[m] >= v) h = m-1; else l = m+1; } if(l<n && a[l]==v) return l; return -1; } void main(){ int v = 9; //int a[] ={1,2,3,3,3,4,5,6,7,8,9}; //int a[] ={1,2,3,4,5,6,6,6,7,8,9}; //fixBug: return m -> return minEqIndex int a[] = {1,2,2,3,3,4,5,6,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,8,8,9,9,9,9}; //int a[] = {8}; //fixBug: minEqIndex == 0 //int a[] = {9,10}; int len = sizeof(a)/sizeof(a[0]); printf("len : %d ",len); for(int i=0;i<len;i++){ printf("[%d]=%d ",i,a[i]); } printf(" "); int m; //m = bin_s_first_eq(a,0,len,v,INT_MIN,INT_MAX); m = bin_s_first_eq2(a,len,v); if(m >= 0) printf("find a[%d]=%d ",m,a[m]); else printf("find m=%d ",m); }
root@ubuntu:~/cdir# gcc bin_search.c -o bin_search.bin -g
root@ubuntu:~/cdir# ./bin_search.bin
len : 2
[0]=9 [1]=10
a[m] a[1]=10 ,maxLtI:-2147483648,minEqI:2147483647
go left
a[m] a[0]=9 ,maxLtI:-2147483648,minEqI:2147483647
find min:0 max:-2147483648
find m=0
root@ubuntu:~/cdir# gcc bin_search.c -o bin_search.bin -g root@ubuntu:~/cdir# ./bin_search.bin len : 29 [0]=1 [1]=2 [2]=2 [3]=3 [4]=3 [5]=4 [6]=5 [7]=6 [8]=7 [9]=7 [10]=7 [11]=7 [12]=7 [13]=7 [14]=7 [15]=7 [16]=7 [17]=7 [18]=7 [19]=7 [20]=7 [21]=7 [22]=7 [23]=8 [24]=8 [25]=9 [26]=9 [27]=9 [28]=9 find a[25]=9
2分查找10有9错
。
//最后一个等于v的 int bs(int[] a,int len, int v){ int l = 0; int r = len-1; int m = (l+r)/2; while(l<=r){ m=(l+r)/2; if(a[m] < v) l=m+1; else if(a[m] > v) r=m-1; else if(m == len-1 || a[m+1] > v) return m; else l=m+1; } return -1; } //第一个小于等于v的 int bs_first_lev(int[] a,int len, int v){ int l=0; int r=len-1; int m=(l+r)/2; while(l<=r){ m=(l+r)/2; if(a[m] >= v) if(m == 0 || a[m-1] < v) return m; else r=m-1; else l=m+1; } return -1; } //第一个大于等于v的 int bs_last_lev(int[] a,int len, int v){ int l=0; int r=len-1; int m=(l+r)/2; while(l<=r){ m=(l+r)/2; if(a[m] <= v) if(m==len-1||a[m+1]>v) return m; else l=m+1; else r=m-1; } return -1; }
一个循环有序数组 4，5，6，1，2，3 如何用二分法找到给定 v值元素？ 先找出数组offset 第一个元素向右移动了3个位置，offset = 3 负数取莫得负数的语言中（JAVA）需要转换一下，一下是按照 负数取莫得到正数的逻辑处理的 额外转换逻辑为 正常情况: A mod B = C （2%5=2) -A mod B = B-A (-2%5=3) 语言特殊情况: -A mod B = -A 时 (-2%5=-2 java中） 修改 (-A + B) mod B = C (-2+5 % 5 = 3) mapIndex = (orgIndex + offset) % arrayLen orgIndex = (mapIndex - offset) % arrayLen int m2o(int m, int offset, int len){ return (mapIndex - offset) % arrayLen; } int o2m(int o, int offset, int len){ return (orgIndex + offset) % arrayLen; } int bs(int[] a,int len, int v, int offset){ int l=o2m(0,offset,len); int r=o2m(len,offset,len); ...每次用下标的时候都转换，这样缺点是效率低,取模指令类似除法，效率不高 }