Sorting and Searching: Most Efficient Code

• November 29th, 2011, 08:29 PM
nicsa
Sorting and Searching: Most Efficient Code
I am trying to create a method to search a sorted array for a value in the most efficient way possible. My teacher doesn't want us to use binary search yet. This is the code I have so far, is there any way to make it more efficient?

Code Java:

```public int sortedSearch(int value) { for(int x=0;x<a.length; x++) if(a[x]<=value) { if(a[x]==value) return x; } return -1; }   private int[] a;```

Thank you.
• November 29th, 2011, 08:54 PM
Junky
Re: Sorting and Searching: Most Efficient Code
Make the inner if statement the first thing the code does in the loop. Why do anything else when you have found the number?

Stop searching as soon as the value in the array is larger than the target number. Currently you continue searching all the way to the end.
• November 29th, 2011, 09:02 PM
nicsa
Re: Sorting and Searching: Most Efficient Code
Code java:

```public int sortedSearch(int value) { for(int x=0;x<a.length; x++) { if(a[x]==value) return x; } return -1; }```

Is this better? I don't think it is efficient still.
• November 29th, 2011, 09:06 PM
Junky
Re: Sorting and Searching: Most Efficient Code
That has addressed my first point but not my second point.
• November 29th, 2011, 09:19 PM
nicsa
Re: Sorting and Searching: Most Efficient Code
public int sortedSearch(int value)
{
int x=0;
while(x<a.length)
{
if(a[x]==value)
{
return x;
}
else
x++;
}
return -1;
}
private int[] a;
• November 29th, 2011, 09:46 PM
Junky
Re: Sorting and Searching: Most Efficient Code
That still does not address my second point.
• November 29th, 2011, 10:04 PM
nicsa
Re: Sorting and Searching: Most Efficient Code
I don't get what you mean
• November 29th, 2011, 10:20 PM
Junky
Re: Sorting and Searching: Most Efficient Code
Imagine you have an array with 1000 numbers in it: 1, 3, 4, 5, etc. Then you attempt to search for 2. When you get to 3 (the second element) you know that 2 is not in the array. However your code continues searching another 998 times. Not very efficient at all. What you need to do is have the loop stop as soon as it knows the target number is not in the array and return -1.