你的位置:首页 > Java教程

[Java教程]在数组中使用二分法查找


package com.db2;import java.util.Arrays;/** * 二分法查找 * * @author denny 使用二分法查找的前提数组已经排过序 * */public class Demo4 {  public static void main(String[] args) {    int[] arr = { 3, 1, 8, 2, 9, 100, 33, 22, 11, 18, 14, 17, 15, 3 };    // 使用Arrays.sort()排序    Arrays.sort(arr);    System.out.println(Arrays.toString(arr));    // 返回结果    //int index = brinarySearch(arr, 99);    int index = brinarySearch_2(arr, 11);    System.out.println("index=" + index);  }  /*   * 二分法查找一返回下标如果是-1就说明没有   */  public static int brinarySearch(int[] arr, int key) {// 数组和要查找的数    int min = 0; // 最小的下标    int max = arr.length - 1;// 最大的下标    int mid = (min + max) / 2;// 中间的下标    while (arr[mid] != key) {      if (key > arr[mid]) { //比中间数还在        min = mid + 1;  //最小的下标=中间下标加一      } else if (key < arr[mid]) {//比中间数还小        max = mid - 1;  //最大的下标=中间下标-1      }       if(max<min){        return -1;      }      mid=(min+max)/2; //再次计算中间下标    }        return mid;  }  /*   * 二分法查找一返回下标如果是-1就说明没有   */  public static int brinarySearch_2(int[] arr, int key) {// 数组和要查找的数    int min = 0; // 最小的下标    int max = arr.length - 1;// 最大的下标    int mid = (min + max) / 2;// 中间的下标      while(min<=max){      if(key>arr[mid]){        min=mid+1;      }else if(key<arr[mid]){        max=mid-1;      }else{        return mid;      }      mid=(min+max)/2;    }    //没找到    return -1;    }  }