當前位置:首頁 » 編程語言 » java折半

java折半

發布時間: 2023-06-04 15:38:42

java實現折半查找 循環結束的條件看不懂

二分法查找(折半查找)的時間復雜度是O(log2n)

即是最壞的情況比較次數是2為底2n的對數。也就數如果數組長度為2,最壞的情況比較2兩次;數組長度為16,最壞的情況比較5次;數組長度1204,最壞的情況是比較11次 就可以找到這個值或者確定找不到這個值。

你的代碼就是通過判斷比較的次數來決定是否結束循環,當已比較(循環)次數大於最壞情況的次數還沒有結束(number != a[middle]),則說明數組中不存在這個值。不過這里是用的N/2來近似的判斷。

另一種更普遍的寫法

publicclassDemo{
publicstaticvoidmain(String[]args){

//你原來的代碼

System.out.println(Arrays.toString(a));
Scannerscanner=newScanner(System.in);
System.out.println("輸入整數,程序判斷該整數是否在數組中:");
intnumber=scanner.nextInt();

intindex=binary(a,number);
if(index==-1){
System.out.printf("%d不在數組中. ",number);
}else{
System.out.printf("%d在數組中,在數組中的位置下標是%d.",number,index);
}
}

privatestaticintbinary(int[]array,intvalue){
intstart=0;
intend=array.length-1;
while(start<=end){
intmiddle=(start+end)/2;
if(value==array[middle]){
returnmiddle;
}elseif(value>array[middle]){
start=middle+1;
}else{
end=middle-1;
}
}
return-1;
}
}

㈡ 用二分法查找(折半查找)java

二分查找也稱折半查找(Binary Search),它是一種效率較高的查找方法。但是,折半查找要求線性表必須採用順序存儲結構,而且表中元素按關鍵字有序排列。

二分查找優缺點

優點是比較次數少,查找速度快,平均性能好;

其缺點是要求待查表為有序表,且插入刪除困難。

因此,折半查找方法適用於不經常變動而查找頻繁的有序列表。
使用條件:查找序列是順序結構,有序。


過程

首先,假設表中元素是按升序排列,將表中間位置記錄的關鍵字與查找關鍵字比較,如果兩者相等,則查找成功;否則利用中間位置記錄將表分成前、後兩個子表,如果中間位置記錄的關鍵字大於查找關鍵字,則進一步查找前一子表,否則進一步查找後一子表。重復以上過程,直到找到滿足條件的記錄,使查找成功,或直到子表不存在為止,此時查找不成功。

利用循環的方式實現二分法查找

public class BinarySearch {
public static void main(String[] args) {
// 生成一個隨機數組 int[] array = suiji();
// 對隨機數組排序 Arrays.sort(array);
System.out.println("產生的隨機數組為: " + Arrays.toString(array));

System.out.println("要進行查找的值: ");
Scanner input = new Scanner(System.in);
// 進行查找的目標值 int aim = input.nextInt();

// 使用二分法查找 int index = binarySearch(array, aim);
System.out.println("查找的值的索引位置: " + index);

}

/** * 生成一個隨機數組 *
* @return 返回值,返回一個隨機數組 */
private static int[] suiji() {
// random.nextInt(n)+m 返回m到m+n-1之間的隨機數 int n = new Random().nextInt(6) + 5;
int[] array = new int[n];
// 循環遍歷為數組賦值 for (int i = 0; i < array.length; i++) {
array[i] = new Random().nextInt(100);
}
return array;
}

/** * 二分法查找 ---循環的方式實現 *
* @param array 要查找的數組 * @param aim 要查找的值 * @return 返回值,成功返回索引,失敗返回-1 */
private static int binarySearch(int[] array, int aim) {
// 數組最小索引值 int left = 0;
// 數組最大索引值 int right = array.length - 1;
int mid;
while (left <= right) {
mid = (left + right) / 2;
// 若查找數值比中間值小,則以整個查找范圍的前半部分作為新的查找范圍 if (aim < array[mid]) {
right = mid - 1;
// 若查找數值比中間值大,則以整個查找范圍的後半部分作為新的查找范圍 } else if (aim > array[mid]) {
left = mid + 1;
// 若查找數據與中間元素值正好相等,則放回中間元素值的索引 } else {
return mid;
}
}
return -1;
}}
運行結果演示:

總結:

遞歸相較於循環,代碼比較簡潔,但是時間和空間消耗比較大,效率低。在實際的學習與工作中,根據情況選擇使用。通常我們如果使用循環實現代碼只要不是太繁瑣都選擇循環的方式實現~

㈢ 用JAVA寫一個完整的折半查找法!!!

import java.util.Scanner;

public class b {

/**
*
* *折半查找法,又稱十分法查找 查找的對象是一個按序排好的數組
*/

public static void main(String[] args) {

int[] initVals = { 9, 12, 37, 53, 67, 71, 89, 122, 290, 435, 555, 888,
1104, 1111, 2222, 3333, 21343, 43256, 56778300 };

for (int i = 0; i < initVals.length; i++)

{

System.out.print(initVals[i] + "、");

}

Scanner cin = new Scanner(System.in);

while (cin.hasNext())

{
int targetVal = cin.nextInt();

b bq = new b();

int postion = bq.query(initVals, targetVal);

if (postion == -1)
System.out.println("沒有找到");

else
System.out.println("要查找的數字在數組中的第 " + (postion + 1) + "個位置");
}
}

/*
*
* 29 29 * @param values 要找的數組對象
*
* 30 30 * @param targetVal 要找的目標數字
*
* 31 31 * @return -1 沒有找到,返回-1
*
* 32 32
*/

public int query(int[] initVals, int targetVal) {

int lowBound = 0;
int upBound = initVals.length - 1;

// 相當於一個指針,指向下一個要比的數字

int nowPostion;

while (true) {

// 指向現在所有數字的中間,沒有整除時向下取整,如7/2=3

nowPostion = (lowBound + upBound) / 2;

// 如果現在這個數字就是了,返回現在的編號

if (initVals[nowPostion] == targetVal) {

return nowPostion;

}

// 如果上界小於下界時,說明已經找完全部了,返回-1表示沒有找到

else if (lowBound > upBound) {

return -1;

}

// 還可以繼續找
else {

// 當前指針的數比targetVal要小,那麼要往小的方向繼續找

if (initVals[nowPostion] < targetVal) {

lowBound = nowPostion + 1;

}

// 當前指針的數比targetVal要大,那麼要往大的方向繼續找

else {

upBound = nowPostion - 1;
}

}
}

}

}

熱點內容
如何更衣櫃密碼鎖密碼設置 發布:2024-03-28 19:42:09 瀏覽:483
如何將一台電腦當雲伺服器嗎 發布:2024-03-28 19:22:39 瀏覽:882
銀行dsk密碼什麼意思 發布:2024-03-28 19:22:35 瀏覽:10
我的世界伺服器怎麼解除ban人 發布:2024-03-28 19:21:47 瀏覽:828
ss怎麼用安卓 發布:2024-03-28 18:51:39 瀏覽:688
腳本注入到其他軟體運行 發布:2024-03-28 18:30:02 瀏覽:721
網易我的世界皮膚能用到伺服器嗎 發布:2024-03-28 18:24:44 瀏覽:805
access資料庫數據類型 發布:2024-03-28 18:16:04 瀏覽:301
安卓界面如何變成蘋果手機界面 發布:2024-03-28 18:07:17 瀏覽:742
方舟手游如何卡安卓大廳會員 發布:2024-03-28 17:52:37 瀏覽:241