Java 二分法检索算法代码实现详解

所属分类：软件编程 / java 阅读数： 65

收藏 0赞 0分享

一，二分法检索算法介绍

二分法检索（binary search）又称折半检索，二分法检索的基本思想是设字典中的元素从小到大有序地存放在数组（array）中。是最常用的搜索算法之一，这主要是由于其搜索时间短。

二，二分法检索算法思路

这种搜索使用分而治之方法，并且需要事先对数据集进行排序。

它将输入集合分为相等的两半，并且每次迭代都将目标元素与中间元素进行比较。

如果找到该元素，则搜索结束。否则，我们根据目标元素是小于还是大于中间元素，通过划分并选择适当的数组分区来继续寻找元素。

这就是为什么对Binary Search有一个排序的集合很重要的原因。

当firstIndex（我们的指针）经过lastIndex（最后一个元素）时，搜索将终止，这意味着我们已经搜索了整个数组，并且该元素不存在。

有两种方法可以实现此算法- 迭代和递归。

这里不应该是关于时间和空间这两个实现之间复杂的差异，虽然这不成立于所有语言。

三，二分法检索算法代码实现

迭代式

首先让我们看一下迭代方法：

public class SearchAlgorithms {
 /**
  *迭代方法
  * @param arr
  * @param elementToSearch
  * @return
  */
 public static int binarySearch(int arr[], int elementToSearch) {
 
  int firstIndex = 0;
  int lastIndex = arr.length - 1;
 
  // 终止条件(元素不存在)
  while(firstIndex <= lastIndex) {
   int middleIndex = (firstIndex + lastIndex) / 2;
   // 如果中间元素是我们的目标元素，那么返回它的索引
   if (arr[middleIndex] == elementToSearch) {
    return middleIndex;
   }
 
   // 如果中间的元素比较小
   // 将我们的指数指向中间+1，不考虑前半部分
   else if (arr[middleIndex] < elementToSearch)
    firstIndex = middleIndex + 1;
 
    // 如果中间的元素更大
    // 将我们的指数指向中间1，不考虑下半部分
   else if (arr[middleIndex] > elementToSearch)
    lastIndex = middleIndex - 1;
 
  }
  return -1;
 }
 /**
  * 用于打印结果
  * @param targetParameter
  * @param index
  */
 public static void print(int targetParameter, int index) {
  if (index == -1){
   System.out.println(targetParameter + " 未找到");
  }
  else {
   System.out.println(targetParameter + " 搜索结果为: " + index);
  }
 }
 //测试一下
 public static void main(String[] args) {
  int index = binarySearch(new int[]{89, 57, 91, 47, 95, 3, 27, 22, 67, 99}, 67);
  print(67, index);
 }
}

输出：

递归的

现在让我们看一下递归实现：

递归方法的区别在于，一旦获得新分区，我们便会调用方法本身。在迭代方法中，每当确定新分区时，我们都会修改第一个和最后一个元素，并在同一循环中重复该过程。

这里的另一个区别是递归调用被推入方法调用堆栈，并且每个递归调用占用一个空间单位。

我们可以像这样使用这种算法：

public class SearchAlgorithms {
 
 /**
  *递归方法
  * @param arr
  * @param elementToSearch
  * @return
  */
 public static int recursiveBinarySearch(int arr[], int firstElement, int lastElement, int elementToSearch) {
 
  // 结束条件
  if (lastElement >= firstElement) {
   int mid = firstElement + (lastElement - firstElement) / 2;
 
   // 如果中间元素是我们的目标元素，那么返回它的索引
   if (arr[mid] == elementToSearch)
    return mid;
 
   // 如果中间元素大于目标元素
   if (arr[mid] > elementToSearch)
    return recursiveBinarySearch(arr, firstElement, mid - 1, elementToSearch);
 
   return recursiveBinarySearch(arr, mid + 1, lastElement, elementToSearch);
  }
 
  return -1;
 }
 /**
  * 用于打印结果
  * @param targetParameter
  * @param index
  */
 public static void print(int targetParameter, int index) {
  if (index == -1){
   System.out.println(targetParameter + " 未找到");
  }
  else {
   System.out.println(targetParameter + " 搜索结果为: " + index);
  }
 }
 //测试一下
 public static void main(String[] args) {
  int index = recursiveBinarySearch(new int[]{3, 22, 27, 47, 57, 67, 89, 91, 95, 99}, 0, 10, 67);
  print(67, index);
 }
}

输出：