我的解决方案在处理边界情况时抛出异常？

huangapple
go评论127阅读模式
英文:

My solution throwing exception with corner cases?

问题

给定一个数组，我需要通过递归和二分查找来打印重复给定元素在数组中的第一个索引，但要处理像数组[0]这样的边界情况，它会抛出“ArrayIsOutOfBound”异常。并且即使我需要通过递归和二分查找来查找重复给定元素在数组中的最后一个索引，对于数组长度处的元素也会出现相同的异常。

  1. 为什么会这样？如何解决这个问题？

要查找最后一个索引-

输入：

  1. int[] array = {5, 10, 10, 10, 10, 20, 20};
  2. int X = 20;

输出应为：

  1. 6

我的输出会抛出异常。

我的解决方案是：

  1. public static void main(String[] args) {
  2.     int[] arr = {5, 10, 10, 10, 10, 20, 20};
  3.     int X = 20;
  4.     System.out.println(lastOcc(arr, 0, arr.length - 1, X));
  5. }
  7. public static int lastOcc(int[] arr, int low, int high, int X) {
  8.     if (low > high) {
  9.         return -1;
  10.     }
  11.     int mid = low + high / 2;
  13.     if (arr[mid] == X) {
  14.         if (mid == arr.length - 1 || arr[mid] != arr[mid + 1]) {
  15.             return mid;
  16.         } else
  17.             return lastOcc(arr, mid + 1, high, X);
  18.     } else if (arr[mid] > X) {
  19.         return lastOcc(arr, low, mid - 1, X);
  20.     } else
  21.         return lastOcc(arr, mid + 1, high, X);
  22. }

要查找第一个索引-

输入：

  1. int[] arr = {10, 20, 20, 30, 40, 50, 60};
  2. int X = 10;

输出应为：

  1. 0

但它会抛出异常。

我的解决方案是：

  1. public static void main(String[] args) {
  2.     int[] arr = {10, 20, 20, 30, 40, 50, 60};
  3.     int x = 10;
  4.     System.out.println(firstOcc(arr, 0, arr.length - 1, x));
  5. }
  7. public static int firstOcc(int[] arr, int low, int high, int x) {
  8.     if (low > high) {
  9.         return -1;
  10.     }
  12.     int mid = low + high / 2;
  14.     if (arr[mid] == x) {
  15.         if (arr[mid - 1] != arr[mid] || mid == 0) {
  16.             return mid;
  17.         } else
  18.             return firstOcc(arr, low, mid - 1, x);
  19.     }
  21.     if (x > arr[mid]) {
  22.         return firstOcc(arr, mid + 1, high, x);
  23.     } else
  24.         return firstOcc(arr, low, mid - 1, x);
  25. }
英文:

Given an array in which I have to print first index of repeating given element in array through recursion
and binary search but with corner case like for array[0] it is throwing exception ArrayIsOutOfBound. And this is happening in every solution even if I have to find last index of repeating given element in array through recursion and binary search for element at array.length -

  1. Why? And how to get rid of this?

To find last index-

Input:

  1. int[] array = {5, 10, 10, 10, 10, 20, 20} 
  3. int X = 20;

Output should be:

  1. 6

My output is throwing exception.

My solution is:

  1. public static void main(String[] args) {
  3.     int[] arr = {5, 10, 10, 10, 10, 20, 20};
  4.     int X = 20;
  5.     System.out.println(lastOcc(arr, 0, arr.length - 1, X));
  6. }
  7. public static int lastOcc(int[] arr, int low, int high, int X) {
  8.     if(low > high){
  9.         return -1;
  10.     }
  11.     int mid = low + high / 2;
  13.     if(arr[mid] == X) {
  14.         if (mid == arr.length - 1 || arr[mid] != arr[mid + 1]) {
  15.             return mid;
  16.         } else
  17.             return lastOcc(arr,mid + 1, high, X);
  18.     } else if (arr[mid] > X) {
  19.         return lastOcc(arr, low, mid - 1, X);
  20.     } else
  21.         return lastOcc(arr, mid + 1, high, X);
  22. }

To find first index-

Input:

  1. int[] arr = {10, 20, 20, 30, 40, 50, 60}
  3. int X = 10;

Output should be:

  1. 0

But it is throwing exception

My Solution is:

  1. public static void main(String[] args) {    
  2.         int[] arr = {10, 20, 20, 30, 40, 50, 60};    
  3.         int x = 10;
  4.         System.out.println(firstOcc(arr, 0, arr.length - 1, x));    
  5.     }
  7.  public static int firstOcc(int[] arr, int low, int high, int x){
  9.         if(low > high){    
  10.             return -1;    
  11.         }
  13.         int mid = low + high / 2;
  15.         if(arr[mid] == x){    
  16.             if(arr[mid  - 1] != arr[mid] || mid == 0){    
  17.                 return mid;    
  18.             } else
  19.                return firstOcc(arr, low, mid - 1, x);
  20.         }
  22.         if(x > arr[mid]){    
  23.             return firstOcc(arr, mid + 1, high, x);    
  24.         } else    
  25.             return firstOcc(arr, low, mid - 1, x);    
  26.     }

答案1

得分: 0

好的，以下是翻译好的内容：

对于此实例，您只需要添加括号

  1. int mid = (low + high) / 2;

更改为

> 在执行加法之前进行除法运算

另外，在 "FirstOccurrence" 中更改

  1. if(arr[mid - 1] != arr[mid] || mid == 0)

为

  1. if(mid == 0 || arr[mid - 1] != arr[mid])

因为这将排除 X=5 的异常情况。

英文:

Well for this instance you only need to add brackets

  1. int mid = (low + high) / 2;

as

> Division is performing prior to addition

And also In "FirstOccurrence" change

  1.  if(arr[mid  - 1] != arr[mid] || mid == 0)  to
  3.  if(mid == 0 || arr[mid  - 1] != arr[mid] )

as this will omit exception for X=5

huangapple
  • 本文由 发表于 2020年9月12日 16:21:20
  • 转载请务必保留本文链接：https://go.coder-hub.com/63858338.html
  • arrays
  • binary-search
  • java
  • recursion
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定