/**
* 測試二分法查找
*/
public class TestBinarySearch {
? ?public static int binarySearch(int[] arr,int tar){
? ? ? ?/*
? ? ? ?使用二分法之前需要對數(shù)組排序 這里設定數(shù)組是由小到大排序
? ? ? ?取中間元素arr[mid]和要查找的數(shù)tar比較 如果tar更大就在中間元素的右側(cè)區(qū)域即比中間元素大的區(qū)域再次取中間元素作比較
? ? ? ?如果tar更小就在左側(cè)區(qū)域再取中間元素比較 區(qū)域每次縮小 一半+mid中間元素本身
? ? ? ?如果一直比較到區(qū)域內(nèi)只有一個元素的時候 mid中間元素就是這個元素 用 arr[mid]和tar比較還是不相同即數(shù)組中不存在tar返回-1
? ? ? ? */

? ? ? ?int low = 0;
? ? ? ?int high = arr.length-1;
? ? ? ?//第一次查詢的區(qū)域是整個數(shù)組 即第0位至length-1位
? ? ? ?int mid;
? ? ? ?//設定中間元素用于比較tar
? ? ? ?while(low<=high){
? ? ? ? ? ?mid = (high+low)/2;
? ? ? ? ? ?//mid不是區(qū)域的長度/2 mid是中間元素的下標 應該在下標low和下標high中間 high-low是長度 (high+low)/2是取平均
? ? ? ? ? ?if(arr[mid] == tar)return mid;
? ? ? ? ? ?if (arr[mid] >tar){
? ? ? ? ? ? ? ?high=mid-1;
? ? ? ? ? ?}
? ? ? ? ? ?if(arr[mid]<tar){
? ? ? ? ? ? ? ?low = mid+1;
? ? ? ? ? ?}
? ? ? ?}
? ? ? ?return -1;
? ?}

? ?public static void main(String[] args) {
? ? ? ?int[] array1 = {5,7,8,1,3,6,4,2,9};
? ? ? ?Arrays.sort(array1);
? ? ? ?//查找之前先要排序
? ? ? ?System.out.println(Arrays.toString(array1));
? ? ? ?System.out.println(binarySearch(array1,8));
? ? ? ?//先查array1[mid=4]<8 范圍變?yōu)閘ow5 high8 mid6 [mid]<8 范圍變?yōu)閘ow7 high8 mid7 [7]=8返回
? ? ? ?System.out.println(binarySearch(array1,0));
? ? ? ?/*
? ? ? ?arr[mid=4]為5>0 arr[mid=1]為2>0 high變?yōu)?-1 while(low0<=high0) mid=(low+high)/2=0
? ? ? ?arr[0]為1>0 high變?yōu)?-1 while(low<=high)false 退出循環(huán)返回-1
? ? ? ? */
? ?}
}