Jared Waxler - 9 months ago 28

Java Question

running into a silly error and I just don't see it. I've been looking at this for a while and don't see what I'm missing. I am recursively searching an array for a specific target number but once I get up to element [7] it begins returning -1. Thanks for taking a look fellas/ladies!

`public static void main(String[] args)`

{

int[] a = {1,25,2,6,4,3,23,30,32,14,11,8};

Arrays.sort(a);

int target = a[7];

int first = a[0];

int last = a.length;

for(int i=0;i<a.length;i++)

{

System.out.print(" "+a[i]);

}

System.out.println("\n"+binarySearch(target,first,last,a));

}

public static int binarySearch(int target,int first, int last, int[] a)

{

int result;

if(first>last)

return -1;

else

{

int mid = (first+last)/2;

if(target == mid)

result = mid;

else if(target<a[mid])

result = binarySearch(target,first,last-1,a);

else

result = binarySearch(target,mid+1,last,a);

}

return result;

}

Answer

In several places you fail to accurately distinguish between the value in an index of an array and the index itself.

This: `a[i]`

gets the value at the ith element

This: `i`

is simply an index, i

With that in mind, here is a fixed version of your code. See my comments in the code for some specific errors I fixed:

```
public static void main(String[] args)
{
int[] a = {1,25,2,6,4,3,23,30,32,14,11,8};
Arrays.sort(a);
int target = a[7];
//here you want the index of the first location to search, not the value in that index
//so you use 0 instead of a[0]
int first = 0;
//the last element index is length-1, not length, since arrays are 0-based
int last = a.length - 1;
for(int i=0;i<a.length;i++)
{
System.out.print(" "+a[i]);
}
System.out.println("\n"+binarySearch(target,first,last,a));
}
public static int binarySearch(int target,int first, int last, int[] a)
{
int result;
if(first>last)
return -1;
else
{
int mid = (first+last)/2;
//here you need to check if the target is equal to the value at the index mid
//before you were checking if the target was equal to the index, which was never true
if(target == a[mid])
//you want to return the value at the target, not the index of the target
//so use a[mid] not mid
result = a[mid];
else if(target<a[mid])
//here you want to search from first to mid-1
//before you were searching from first to last-1, which is not correct binary search
result = binarySearch(target,first,mid - 1,a);
else
result = binarySearch(target,mid + 1,last,a);
}
return result;
}
```

Source (Stackoverflow)