首页 > 代码库 > [leetcode]二分查找总结
[leetcode]二分查找总结
Search for a Range
1.最简单的想法，用最普通的二分查找，找到target,然后向左右扩张，大量的重复的target，就会出现O(n)效率。
class Solution { public int[] searchRange(int[] A, int target) { int ans[]=new int[2]; int a= bserch(A,target); if(a==-1) {ans[0]=-1;ans[1]=-1; return ans;} //left int b=a-1; while(b>=0&&A[b]==target) b--; ans[0]=b+1; b=a+1; while(b<=A.length-1&&A[b]==target) b++; ans[1]=b-1; return ans; } public int bserch(int A[],int target) { int low=0; int end=A.length-1; while(low<=end) { int mid=(low+end)>>1; if(A[mid]==target) return mid; else if(A[mid]<target) low=mid+1; else end=mid-1; } return -1; } }
2.二分查找加入第一个大的位置（上届），第一个大于等于它的位置（下界）
1 class Solution { 2 public int[] searchRange(int[] A, int target) { 3 int ans[]=new int[2]; 4 int a= bserch(A,target); 5 if(a==-1) {ans[0]=-1;ans[1]=-1; return ans;} 6 //left 7 int b=a-1; 8 while(b>=0&&A[b]==target) b--; 9 ans[0]=b+1;10 b=a+1;11 12 while(b<=A.length-1&&A[b]==target) b++;13 ans[1]=b-1;14 return ans;15 16 17 18 19 }20 21 public int bserch(int A[],int target)22 {23 int low=0;24 int end=A.length-1;25 while(low<=end)26 {27 int mid=(low+end)>>1;28 if(A[mid]==target) return mid;29 else if(A[mid]<target) low=mid+1;30 else end=mid-1;31 32 }33 34 return -1;35 }36 public int upperbound(int A[],int target) // the first one larger than target37 {38 int low=0;39 int end=A.length-1;40 while(low<=end)41 {42 int mid=(low+end)>>1;43 if(A[mid]>target) end=mid-1;44 else low=mid+1;45 46 }47 return low;48 }49 public int lowbound(int A[],int target) // the first one larger or equal target50 {51 int low=0;52 int end=A.length-1;53 while(low<=end)54 {55 int mid=(low+end)>>1;56 if(A[mid]>=target) end=mid-1;57 else low=mid+1;58 59 }60 return low;61 }62 63 64 65 66 67 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。