Java递归和非递归二分查找

矫情吗；* 2022-02-02 04:49 349阅读 0赞

非递归实现二分查找

  1. /** * 非递归查找key * @param array * @param key * @return */
  2.     public static int binarySearch(int[] array, int key) { 
  3.         bubbleSort(array);
  4.         int left = 0;
  5.         int right = array.length - 1;
  6.         int mid;
  7.         while (left <= right) { 
  8.             mid = (left + right) / 2;
  9.             if (array[mid] == key) { 
  10.                 return mid + 1;
  11.             } else if (array[mid] < key) { 
  12.                 left = mid + 1;
  13.             } else { 
  14.                 right = mid - 1;
  15.             }
  16.         }
  17.         return -1;
  18.     }

递归实现二分查找

  1. /** * 递归查找key * * @param array * @param key * @param left * @param right * @return */
  2.     public static int sort(int[] array, int key, int left, int right) { 
  3.         if (left <= right) { 
  4.             int mid = left + right;
  5.             if (key == array[mid]) { 
  6.                 return mid + 1;
  7.             } else if (key < array[mid]) { 
  8.                 return sort(array, key, left, mid - 1);
  9.             } else { 
  10.                 return sort(array, key, mid + 1, right);
  11.             }
  13.         }
  14.         return -1;
  15.     }

查询第一个出现元素的位置

  1. /** * 查询第一个元素出现的位置 * * @param array * @param key * @return */
  2.     public static int biSearchFirst(int[] array, int key) { 
  3.         int len = array.length;
  4.         int left = 0;
  5.         int right = len - 1;
  6.         int mid = 0;
  7.         while (left < right) { 
  8.             mid = (left + right) >> 1;
  9.             if (array[mid] < key) { 
  10.                 left = mid + 1;
  11.             } else { 
  12.                 right = mid;
  13.             }
  14.         }
  15.         if (array[left] != key) { 
  16.             return -1;
  17.         } else { 
  18.             return left;
  19.         }
  20.     }

查询最后一个出现元素的位置

  1. /** * 查询元素最后一次出现的位置 * * @param array * @param key * @return */
  2.     public static int biSearchLast(int[] array, int key) { 
  3.         int len = array.length;
  4.         int left = 0;
  5.         int right = len - 1;
  6.         int mid = 0;
  7.         while (left < right) { 
  8.             mid = (left + right + 1) >> 1;
  9.             if (array[mid] <= key) { 
  10.                 left = mid;
  11.             } else { 
  12.                 right = mid - 1;
  13.             }
  14.         }
  15.         if (array[left] != key) { 
  16.             return -1;
  17.         } else { 
  18.             return right;
  19.         }
  20.     }

发表评论

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

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

相关阅读