• 這次不排序了，對(duì)排好序的數(shù)組做個(gè)查找吧

介紹

• 二分查找排序英文名為BinarySort，是一種效率較高的查找方法
• 要求線性表必須采用順序存儲(chǔ)結(jié)構(gòu)

基本思路

• 通過(guò)不斷地將搜索范圍縮小一半來(lái)找到目標(biāo)元素：
  • 1、假定數(shù)組為arr，需要查找的值為target
  • 2、定義left、right 和mid三個(gè)索引。mid=(left+right)/2；
  • 3、如果中間元素正好是要查找的元素，搜索結(jié)束；
    （ 即arr[mid]==target，結(jié)束）
  • 4、如果目標(biāo)元素大于中間元素，那么在數(shù)組的右半部分繼續(xù)查找
    （ 即arr[mid]>target，循環(huán)或者遞歸右半部分）
  • 5、如果目標(biāo)元素小于中間元素，那么在數(shù)組的左半部分繼續(xù)查找
    （ 即arr[mid]<target，循環(huán)或者遞歸左半部分）
  • 6、重復(fù)以上步驟，直到找到目標(biāo)元素或者搜索范圍為空（找不到目標(biāo)值）

代碼

• 循環(huán)方法

  public static void main(String[] args) {int[] arr = {1,10, 20, 30, 40, 50, 60, 70, 80, 90};sort(arr,60);sort(arr,45);sort(arr,1);
  }public static int sort(int[] arr,int target){int left = 0;int right = arr.length-1;while(left<=right){ // 此處=是為了當(dāng)索引移動(dòng)后只剩一個(gè)時(shí)，也需要比較int mid = (left+right)/2; // 放在while循環(huán)外邊就成了固定值了if(arr[mid]==target){System.out.println("找到了！");return mid;}else if(arr[mid]<target){ // 目標(biāo)值比中間值大，要往右邊查找left = mid+1;}else{    // 目標(biāo)值比中間值小，要往左邊查找right = mid-1;}}System.out.println("沒(méi)有該數(shù)值");return -1;
  }
  ------------輸出結(jié)果--------------
  找到了【60】，位置是：6
  數(shù)值【45】不存在
  找到了【1】，位置是：0
  

• 遞歸方法

  public static void main(String[] args) {int[] arr = {1,10, 20, 30, 40, 50, 60, 70, 80, 90};digui(arr,60,0,arr.length-1);digui(arr,45,0,arr.length-1);digui(arr,1,0,arr.length-1);
  }
  public static int digui(int[] arr,int target,int left,int right){if(left>right){System.out.println("不存在該數(shù)值");return -1;}int mid = (left+right)/2;if(arr[mid]==target){System.out.println("找到了！");return mid;}else if(arr[mid]>target){ // 目標(biāo)值比中間值小return digui(arr,target,left,mid-1);}else{return digui(arr,target,mid+1,right);}
  }
  ------------輸出結(jié)果--------------
  找到了【60】，位置是：6
  數(shù)值【45】不存在
  找到了【1】，位置是：0
  

老規(guī)矩，來(lái)個(gè)流程圖

• 希望這三張圖能幫忙大家理解為什么left<=right
  
  
  

時(shí)間復(fù)雜度

• 最好情況是O(1)，即一下就找到了
• 平均是O(logN)