資訊專欄INFORMATION COLUMN
摘要：寫二分法時需要判斷循環(huán)何時終止，如果每次都是，，會導(dǎo)致循環(huán)無法終止，所以此處用了。遞歸實現(xiàn)二分法目標數(shù)組，目標值，左邊界，右邊界輸入的數(shù)組是
//非遞歸實現(xiàn)二分法
public class Jianzhi{
public static void main (String[] args){
int[] num = {1,2,3,4,5,100};
int m = find(num , 5) ;
System.out.println(m);
}
public static int find(int[] list , int m ){
if(list == null ){
System.out.println("輸入的數(shù)組長度出錯。") ;
}else if(list.length ==1 ){ //如果傳入的數(shù)組只有一個數(shù)字
int n = list[0]==m?0:-1 ;
return n ;
}else {
int left = 0 ;
int right = list.length-1 ;
while(left <= right){
int mid = (left + right)/ 2 ;
if(list[mid]==m){
return mid ;
}else if (list[mid]m){
right = mid - 1 ;
}
}
System.out.println("未在數(shù)組中找到數(shù)字"+m);
}
return -1 ;
}
}
//注意： 1.需要把mid放入循環(huán)中，不能放在循環(huán)體外，因為每次都要把mid賦值給left或者right如果放在外面每次賦值的數(shù)都一樣會死循環(huán)。
// 2.寫二分法時需要判斷循環(huán)何時終止，如果每次都是left=mid，right=mid，會導(dǎo)致循環(huán)無法終止
// ，所以此處用了left=mid+1 right=mid-1 。這樣做還有一個好處：發(fā)現(xiàn)mid不是所要找的數(shù)時，就直接舍棄，讓left和right不指向這個節(jié)點。
——————————————————————————————————————————————————
//遞歸實現(xiàn)二分法
public class Jianzhi{
// （目標數(shù)組，目標值，左邊界，右邊界）
public static int find(int[] list , int m ,int begin , int end) {
if(list == null){
System.out.println("輸入的數(shù)組是null");
return -1 ;
}
if(list.length == 1 ){
return list[0]==m?0:-1 ;
}
if(begin > end){
return -1 ;
}
int mid = (begin + end) / 2 ;
if(list[mid] == m){
return mid ;
}else if (list[mid] < m ){
return find(list , m ,mid+1 , end );
}else if (list[mid] > m ){
return find(list , m , begin , mid-1 );
}
return -1 ;
}
public static void main (String[] args){
int[] num = {1,2,3,4,5,100};
int m = find(num , 1,0,num.length-1) ;
System.out.println(m);
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/71375.html
摘要：二分查找的定義二分查找也稱折半查找，它是一種效率較高的查找方法。但是，折半查找要求線性表必須采用順序存儲結(jié)構(gòu)，而且表中元素按關(guān)鍵字有序排列。算法的要求從上面的定義我們可以知道，滿足該算法的要求必須如下兩點必須采用順序存儲結(jié)構(gòu)。 showImg(https://segmentfault.com/img/remote/1460000016466416?w=800&h=191); 二分查找的...
摘要：數(shù)據(jù)項是數(shù)據(jù)的不可分割的最小單位。數(shù)據(jù)項是對客觀事物某一方面特性的數(shù)據(jù)描述。數(shù)據(jù)對象是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)元素之間的相互關(guān)系稱為邏輯結(jié)構(gòu)。 項目地址 https://github.com/m9rco/algo... 每周最少一更，求出題，求虐待 At least once a week, ask for problems and abuse 簡...
摘要：數(shù)據(jù)項是數(shù)據(jù)的不可分割的最小單位。數(shù)據(jù)項是對客觀事物某一方面特性的數(shù)據(jù)描述。數(shù)據(jù)對象是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)元素之間的相互關(guān)系稱為邏輯結(jié)構(gòu)。 項目地址 https://github.com/m9rco/algo... 每周最少一更，求出題，求虐待 At least once a week, ask for problems and abuse 簡...
摘要：數(shù)據(jù)項是數(shù)據(jù)的不可分割的最小單位。數(shù)據(jù)項是對客觀事物某一方面特性的數(shù)據(jù)描述。數(shù)據(jù)對象是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)元素之間的相互關(guān)系稱為邏輯結(jié)構(gòu)。 項目地址 https://github.com/m9rco/algo... 每周最少一更，求出題，求虐待 At least once a week, ask for problems and abuse 簡...
閱讀 2470·2021-09-28 09:36
閱讀 3612·2021-09-22 15:41
閱讀 4418·2021-09-04 16:45
閱讀 2013·2019-08-30 15:55
閱讀 2853·2019-08-30 13:49
閱讀 834·2019-08-29 16:34
閱讀 2379·2019-08-29 12:57
閱讀 1691·2019-08-26 18:42
