Java中常用的查找方法——順序查找和二分查找(共6頁(yè))

1、精選優(yōu)質(zhì)文檔-傾情為你奉上Java中常用的查找算法順序查找和二分查找1、 順序查找：a) 原理：順序查找就是按順序從頭到尾依次往下查找，找到數(shù)據(jù)，則提前結(jié)束查找，找不到便一直查找下去，直到數(shù)據(jù)最后一位。b) 圖例說(shuō)明：原始數(shù)據(jù)：int a=4,6,2,8,1,9,0,3;要查找數(shù)字：8代碼演示：import java.util.Scanner;/* * 順序查找 */public class SequelSearch public static void main(String arg) int a=4,6,2,8,1,9,0,3;Scanner input=new Scanner(Syste

2、m.in);System.out.println("請(qǐng)輸入你要查找的數(shù)：");/存放控制臺(tái)輸入的語(yǔ)句int num=input.nextInt();/調(diào)用searc()方法，將返回值保存在result中 int result=search(a, num); if(result=-1) System.out.println("你輸入的數(shù)不存在與數(shù)組中。"); else System.out.println("你輸入的數(shù)字存在，在數(shù)組中的位置是第："+(result+1)+"個(gè)");public static int

3、search(int a, int num) for(int i = 0; i < a.length; i+) if(ai = num)/如果數(shù)據(jù)存在 return i;/返回?cái)?shù)據(jù)所在的下標(biāo)，也就是位置 return -1;/不存在的話返回-1運(yùn)行截圖：2、 二分查找a) 前提條件：已排序的數(shù)組中查找b) 二分查找的基本思想是：首先確定該查找區(qū)間的中間點(diǎn)位置： int mid = (low+upper) / 2；然后將待查找的值與中間點(diǎn)位置的值比較：若相等，則查找成功并返回此位置。若中間點(diǎn)位置值大于待查值，則新的查找區(qū)間是中間點(diǎn)位置的左邊區(qū)域。若中間點(diǎn)位置值小于待查值，則新的查找區(qū)間是中

4、間點(diǎn)位置的右邊區(qū)域。下一次查找是針對(duì)新的查找區(qū)間進(jìn)行的。c) 圖例說(shuō)明：原始數(shù)據(jù)：int a=5,3,6,1,9,8,2,4,7;查找是否存在數(shù)字8；第一步，先用之前學(xué)過(guò)的排序方法將數(shù)組按升序排序：int a=1,2,3,4,5,6,7,8,9;第二步，取中間數(shù)：5跟8比較，8大于5 ，取中間數(shù)右側(cè)的數(shù)組進(jìn)行比較，即6,7,8,9第三步：重復(fù)第一步和第二步，直到找到數(shù)據(jù)或者比較完所有數(shù)據(jù)。d) 代碼示例：import java.util.Scanner;/* * 二分查找 */public class BinarySearch public static void main(String ar

5、gs) int arr=5,3,6,1,9,8,2,4,7;/先打印輸出原始數(shù)組數(shù)據(jù)System.out.println("原始數(shù)組數(shù)據(jù)如下：");for (int n : arr) System.out.print(n+" ");System.out.println();/首先對(duì)數(shù)組進(jìn)行排序，這里用冒泡排序for(int i=0;i<arr.length-1;i+)for(int j=0;j<arr.length-1-i;j+)if(arrj>arrj+1)int temp=arrj;arrj=arrj+1;arrj+1=temp;/

6、遍歷輸出排序好的數(shù)組System.out.println("經(jīng)過(guò)冒泡排序后的數(shù)組：");for(int n:arr)System.out.print(n+" ");System.out.println();/換行Scanner input=new Scanner(System.in);System.out.println("請(qǐng)輸入你要查找的數(shù)：");int num=input.nextInt();int result=binarySearch(arr, num);if(result=-1)System.out.println("你要查找的數(shù)不存在");elseSystem.out.println("你要查找的數(shù)存在，在數(shù)組中的位置是："+result);/二分查找算法public static int binarySearch(int arr,int num)int low=0;/數(shù)組第一位數(shù)int upper=arr.length-1;/數(shù)組最后一位數(shù)while(low<=upper)/循環(huán)條件int mid=(upper+