首页 > 代码库 > 再探二分查找
再探二分查找
public class BiSearchChangeMode1{ public static void main(String args[]){ double[] a = {1,2.5,2.5,2.5,2.5,2.5,3,4,4,4,5}; int len = a.length; double key = 25; //四组测试数据(-2,2,2.5,25) int resIndex = getTheMinThanKey(a,len,key,0,len-1); System.out.println("+++++++++++++++++++++++++++++++++++"); System.out.println("1.在一个有序的数组中,找到一个最小的比key大的数(即,第一个比key大的数)"); if(resIndex != -1){ System.out.println("\t数组的下标为:" + resIndex); System.out.println("\t数组的值为:" + a[resIndex]); }else{ System.out.println("\t数组中没有满足条件的值"); } System.out.println("+++++++++++++++++++++++++++++++++++"); System.out.println("2.在一个有序的数组中,找到和key相等的最小下标的数(即,第一个和key相等的数)"); resIndex = getTheFirstEqualsNum(a,len,key,0,len-1); if(resIndex != -1){ System.out.println("\t数组的下标为:" + resIndex); System.out.println("\t数组的值为:" + a[resIndex]); }else{ System.out.println("\t数组中没有满足条件的值"); } System.out.println("+++++++++++++++++++++++++++++++++++"); System.out.println("3.在一个有序的数组中,找到和key相等的最大下标的数(即,最后一个和key相等的数)"); resIndex = getTheLastEqualsNum(a,len,key,0,len-1); if(resIndex != -1){ System.out.println("\t数组的下标为:" + resIndex); System.out.println("\t数组的值为:" + a[resIndex]); }else{ System.out.println("\t数组中没有满足条件的值"); } System.out.println("+++++++++++++++++++++++++++++++++++"); System.out.println("4.在一个有序的数组中,找到和key相等的数(任意一个),不存在则返回-1"); resIndex = getAnyEqualsNum(a,key,0,len-1); if(resIndex != -1){ System.out.println("\t数组的下标为:" + resIndex); System.out.println("\t数组的值为:" + a[resIndex]); }else{ System.out.println("\t数组中没有满足条件的值"); } System.out.println("+++++++++++++++++++++++++++++++++++"); System.out.println("5.在一个有序的数组中,找到一个最大的比key小的数(即,最后一个比key小的数)"); resIndex = getTheMaxLessKey(a,len,key,0,len-1); if(resIndex != -1){ System.out.println("\t数组的下标为:" + resIndex); System.out.println("\t数组的值为:" + a[resIndex]); }else{ System.out.println("\t数组中没有满足条件的值"); } } /** * 1 在一个有序的数组中,找到一个最小的比key大的数(即,第一个比key大的数) */ public static int getTheMinThanKey(double[] a,int len,double key,int low,int high){ //1:如果第一个数就比key大 if(a[0]>key){ return 0; } //2:如果最后一个数不大于key if(a[len-1]<=key){ return -1; } //3 :其他情况 if(high>=1 && a[high]>key && a[high-1]<=key){ return high; } while(low < high-1){ int mid = low + (high-low)/2; if(a[mid]>key) high = mid; else low = mid; } return getTheMinThanKey(a,len,key,low,high); } /** * 2 在一个有序的数组中,找到和key相等的最小下标的数(即,第一个和key相等的数) */ public static int getTheFirstEqualsNum(double[] a,int len,double key,int low,int high){ //1:没有满足条件的 if(low>high){ return -1; } //2:第一个数即满足条件时 if(a[0] == key){ return 0; } //3:其他情况 if(high>=1 && a[high]==key && a[high-1] != key){ return high; } while(low<=high){ int mid = low + (high-low)/2; if(a[mid]>key) high = mid-1; else if(a[mid]<key) low = mid+1; else{ high = mid; break; } } return getTheFirstEqualsNum(a,len,key,low,high); } /** * 3 在一个有序的数组中,找到和key相等的最大下标的数(即,最后一个和key相等的数) */ public static int getTheLastEqualsNum(double[] a,int len,double key,int low,int high){ //1:没有满足条件的 if(low>high){ return -1; } //2:最后一个数即满足条件时 if(a[len-1] == key){ return len-1; } //3:其他情况 if(low<len-1 && a[low]==key && a[low+1] != key){ return low; } while(low<=high){ int mid = low + (high-low)/2; if(a[mid]>key) high = mid-1; else if(a[mid]<key) low = mid+1; else{ low = mid; break; } } return getTheLastEqualsNum(a,len,key,low,high); } /** * 4 在一个有序的数组中,找到和key相等的数(任意一个),不存在则返回-1 */ public static int getAnyEqualsNum(double[] a,double key,int low,int high){ while(low<=high){ int mid = low + (high-low)/2; if(a[mid]>key){ high = mid - 1; }else if(a[mid]<key){ low = mid + 1; }else{ return mid; } } return -1; } /** * 5 在一个有序的数组中,找到一个最大的比key小的数(即,最后一个比key小的数) */ public static int getTheMaxLessKey(double[] a,int len,double key,int low,int high){ //1:如果最后一个数比key小 if(a[len-1]<key){ return len-1; } //2:如果第一个比key大 if(a[0]>key){ return -1; } if(low<len-1 && a[low]<key && a[high]>=key){ return low; } while(low<high-1){ int mid = low + (high-low)/2; if(a[mid]>key){ high = mid; }else{ low = mid; } } return getTheMaxLessKey(a,len,key,low,high); }}
再探二分查找
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。