欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

2021.04.09折半查找算法

程序员文章站 2024-03-19 14:44:16
...

折半查找算法

折半查找(二分查找)的原理:

不使用递归来进行折半查找,代码如下:

public class BinarySearch {
   public static void main(String[] args) {
      int[] array = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
      System.out.println(searchLoop(array, 101));
   }
   public static int searchLoop(int[] array, int findValue) {
      // 如果数组为空,直接返回-1,即查找失败
      if (array == null) { return -1;  }
      // 起始位置
      int start = 0;
      // 结束位置
      int end = array.length - 1;
      while (start <= end) {
         // 中间位置
         int middle = (start + end) / 2;
         // 中值
         int middleValue = array[middle];
         if (findValue == middleValue) {
            // 等于中值直接返回
            return middle;
         } else if (findValue < middleValue) {
            // 小于中值时在中值前面找
            end = middle - 1;
         } else {
            // 大于中值在中值后面找
            start = middle + 1;
         }
      }
      // 返回-1,即查找失败
      return -1;
   }
}

使用递归进行折半查找,代码如下:

public class BinarySearch {
   public static void main(String[] args) {
      int[] array = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
      System.out.println(binSearch(array, 10));
   }
   public static int binSearch(int array[], int key) {
      int start = 0;
      int end = array.length - 1;
      return binSearch(array, start, end, key);
   }
   public static int binSearch(int array[], int start, int end, int key) {
      int mid = (end + start) / 2;
      if (start > end) {
         return -1;
      }
      if (array[mid] == key) {
         return mid;
      } else if (key > array[mid]) {
         return binSearch(array, mid + 1, end, key);
      } else {
         return binSearch(array, start, mid - 1, key);
      }
   }
}