Java中实现二分查找的两种方法，如何改写为一个长尾词？

本文共计507个文字，预计阅读时间需要3分钟。

Java实现二分查找有两种方法：递归和非递归。以下是详细说明：

递归二分查找

递归方法利用函数自身调用自身来实现二分查找。

javapublic static int recursionBinarySearch(int[] arr, int key) { return recursionBinarySearch(arr, key, 0, arr.length - 1);}

private static int recursionBinarySearch(int[] arr, int key, int left, int right) { if (left > right) { return -1; } int mid=(left + right) / 2; if (arr[mid]==key) { return mid; } else if (arr[mid] > key) { return recursionBinarySearch(arr, key, left, mid - 1); } else { return recursionBinarySearch(arr, key, mid + 1, right); }}

非递归二分查找

非递归方法使用循环来实现二分查找。

javapublic static int nonRecursionBinarySearch(int[] arr, int key) { int left=0; int right=arr.length - 1; while (left key) { right=mid - 1; } else { left=mid + 1; } } return -1;}

以上是Java实现二分查找的两种方法，具体实现和原理可以参考以下链接：

- [递归二分查找](http://blog.csdn.net/maoyuanming0806/article/details/78176957)- [非递归二分查找](http://blog.csdn.net/maoyuanming0806/article/details/78176957)

java实现二分查找两种方法

详细说明参考：blog.csdn.net/maoyuanming0806/article/details/78176957 /** * 使用递归的二分查找 *title:recursionBinarySearch *@param arr 有序数组 *@param key 待查找关键字 *@return 找到的位置 */ public static int recursionBinarySearch(int[] arr,int key,int low,int high){ if(key < arr[low] || key > arr[high] || low > high){ return -1; } int middle = (low + high) >>> 1; //初始中间位置 if(arr[middle] > key){ //比关键字大则关键字在左区域 return recursionBinarySearch(arr, key, low, middle - 1); }else if(arr[middle] < key){ //比关键字小则关键字在右区域 return recursionBinarySearch(arr, key, middle + 1, high); }else { return middle; } } 方法二： /** * 不使用递归的二分查找 *title:commonBinarySearch *@param arr *@param key *@return 关键字位置 */ public static int commonBinarySearch(int[] arr,int key){ int low = 0; int high = arr.length - 1; int middle = 0; //定义middle if(key < arr[low] || key > arr[high] || low > high){ return -1; } while(low <= high){ middle = (low + high) >>> 1; if(arr[middle] > key){ //比关键字大则关键字在左区域 high = middle - 1; }else if(arr[middle] < key){ //比关键字小则关键字在右区域 low = middle + 1; }else{ return middle; } } return -1; //最后仍然没有找到，则返回-1 }