Java编程：二分查找算法实现代码

二分查找算法

又叫折半查找，要求待查找的序列有序。每次取中间位置的值与待查关键字比较，如果中间位置的值比待查关键字大，则在前半部分循环这个查找的过程，如果中间位置的值比待查关键字小， 则在后半部分循环这个查找的过程。直到查找到了为止，否则序列中没有待查的关键字。

注意：排序规则与数组的排序顺序有关, 即从大到小排序和从小到大排序是不一样的，并且乱序是不能用二分查找算法的。

下面用代码实现进一步了解二分查找算法： 方法一：循环

public static void main(String[] args) {
          
   
  Scanner sc = new Scanner(System.in);
//  int []arr = {1,2,3,3,4,10};
//  int target = 3;
  int []arr = {
          
   1,2,3,3,4,10};
  int target = 6 ;//设定要查找的元素
  //调用binarySearch()方法查找该元素在arr数组中的下标位置
  int index = binarySearch(arr, target);
  System.out.println(index);//打印输出这个元素的下标
 }
 //二分查找方法
 public static int binarySearch(int []arr,int num) {
          
   
  int min = 0;//起始元素
  int max = arr.length-1;//结束元素
  int mid = 0;//中间元素
  while(min<=max) {
          
   
   mid = (max+min)/2;
   if(num<arr[mid]) {
          
   
    max = mid-1;
   }if(num>arr[mid]) {
          
   
    min = mid+1;
   }if(num==arr[mid]) {
          
   
    return mid;//找到了
   }
  }
  return -1;//未找到
 }

方法二：递归

public static void main(String[] args) {
          
   
//  int []arr = {1,2,3,3,4,10};
//  int target = 3;
  int []arr = {
          
   1,4,4,5,7,7,8,9,9,10};
  int target = 1;
  int index = binarySearch(arr, target,0,arr.length-1);
  System.out.println(index);
 }
 //二分查找方法
 //arr 该数组  num 要查找的数 min 初始元素 max结束元素
 public static int binarySearch(int []arr,int num,int min,int max) {
          
   
  int mid = (min+max)/2;//中间元素
  if(min>max) {
          
   
   return -1;//递归结束，没找到
  }
  //查找的数比中间元素小，返回中间元素最右边的元素
  if(num<arr[mid]) {
          
   
   return binarySearch(arr, num, min, mid-1);
   //查找的数比中间元素大，返回中间元素最左边的元素
  }else if(num>arr[mid]) {
          
   
   return binarySearch(arr, num, mid+1, max);
  }else {
          
   
   return mid;//找到了
  }
 }