递归（5）—— 二分查找的递归解法

曾经终败给现在 2022-12-02 03:55 255阅读 0赞

分析：

  全范围内二分查找 等价于三个子问题：
    左边找（递归）
    中间找
    右边找（递归）
  注意：左边找和右边找只选其一。

代码实现：

  1. public class _15二分查找的递归解法 { 
  2.     public static void main(String[] args) { 
  3.         int arr[] = { 1,2,3,4,5};
  4.         System.out.println(binarySearch(arr,0,4,4));
  5.     }
  7.     //arr：传入的数组 
  8.     //low、high：数组的最低和最高下标 
  9.     //key:待查找的元素
  10.     private static int binarySearch(int[]arr,int low,int high,int key) { 
  11.         if (low>high) { 
  12.             return -1;
  13.         }
  14.         int mid = low+((high-low)>>1);
  15.         int midVal = arr[mid];
  16.         if (midVal < key) { 
  17.             return binarySearch(arr, mid+1, high, key);
  18.         }else if (midVal>key) { 
  19.             return binarySearch(arr, low, high-1, key);
  20.         }else { 
  21.             return mid;
  22.         }
  23.     }
  24. }

运行结果：

在这里插入图片描述

发表评论

表情：
评论列表 （有 0 条评论，255人围观）

还没有评论，来说两句吧...

相关阅读