二分法查找，顧名思義就是要將數據每次都分成兩份然后再去找到你想要的數據，我們可以這樣去想，二分法查找很類似與我們平時玩的猜價格游戲，當你報出一個價格時裁判會告訴你價格相對于真實值的高低，倘若是低了那我們一定會再說出一個略高的價格，反之亦然。在二分法查找時要求傳入的數據必須已經有序，假設現在為升序，然后每次將所尋找的值與中間值(數組左邊界+(右邊界-左邊界)/2)作比較，大了則去尋找中間值左側數據，小則尋找中間值右側數據。
二分法查找比較局限性的就是只能操作一個已經排序了的數組。
方法一
下面為一個二分法實現的完整代碼
package dichotomy;import java.util.Arrays;import java.util.Scanner;import static java.lang.System.out;public class Erchange { private static Scanner in; public int find(int a[],int b) //a為所要查找的數 { int mid,low=0,high; high=a.length-1; while(low<=high) { mid=low+(high-low)/2; if(b<a[mid]) { high=mid-1; } else if(b>a[mid]) { low=mid+1; } else { return mid+1; } } return 0; } public static void main(String[] args) { int a[]; int t; int sum=0; Erchange p=new Erchange(); int q2 = 0; in = new Scanner(System.in); out.println("請輸入數組長度"); q2= in.nextInt(); a=new int [q2]; out.println("請輸入數組元素"); for(int i=0;i<a.length;i++) { a[i]=in.nextInt(); } out.println("排序后數組為"); Arrays.sort(a); for (int i = 0; i < a.length; i++) { out.print(a[i]+" "); } out.println(); out.println("請輸入所要查找的數若未查找到該數則輸出-1"); q2=in.nextInt(); for(int i=0;i<a.length;i++) { if(q2==a[i]) { t=1; } else { t=0; } sum=sum+t; } if(sum==0) { out.println("-1"); } else { out.println("所輸入的數在第"+p.find(a,q2)+"位"); }}方法二
代碼實現：
public class BinarySearch {//進行二分法查找的前提是數組已經有序！ public static int rank(int key,int nums[]) { //查找范圍的上下界 int low=0; int high=nums.length-1; //未查找到的返回值 int notFind=-1; while(low<=high) { //二分中點=數組左邊界+(右邊界-左邊界)/2 //整數類型默認取下整 int mid=low+(high-low)/2; //中間值是如果大于key if(nums[mid]>key) { //證明key在[low,mid-1]這個區間 //因為num[mid]已經判斷過了所以下界要減一 high=mid-1; }else if(nums[mid]<key) { //證明key在[mid+1,high]這個區間 //同樣判斷過mid對應的值要從mid+1往后判斷 low=mid+1; } else { //查找成功 return mid; } } //未成功 return notFind; } public static void main(String[] args) { System.out.println("請輸入數據數量："); Scanner scanner=new Scanner(System.in); int amount=scanner.nextInt(); int num; int nums[]=new int[amount]; int i=0; while(i<amount) { nums[i]=scanner.nextInt(); i++; } Arrays.sort(nums); System.out.println("請輸入想要查找的值"); int key=scanner.nextInt(); int answer=rank(key,nums); if(answer!=-1) { System.out.println("所查找的數據存在："+nums[answer]); } else { System.out.println("您所查找的數據不存在"); } } }方法三、算法代碼實現之二分法查找
封裝成類：
package com.roc.algorithms.search; /** * 二分法查找 * * @author roc */public class BinarySearch { /** * @param a 升序排列的數組 * @param k 待查找的整數 * @return 如果查到有就返回對應角標，沒有就返回-1 */ public static int search(int[] a, int k) { int lo = 0, hi = a.length - 1; while (lo <= hi) { int m = (lo + hi) >> 1; if (a[m] < k) { lo = m + 1; } else if (a[m] > k) { hi = m - 1; } else { return m; } } return -1; }}測試：
int[] a = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};System.out.println(BinarySearch.search(a, 6));輸出：
6
以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持VeVb武林網。
新聞熱點
疑難解答
圖片精選
