The aim of this exercise is to check the presence of a number in an array.
Specifications: The items are integers arranged in ascending order. The array can contain up to 1 million items. The array is never null. Implement the method boolean Answer.Exists(int[] ints, int k) so that it returns true if k belongs to ints, otherwise the method should return false.
Important note: Try to save CPU cycles if possible.
this is my code
import static java.sql.DriverManager.println;
import java.util.*;
class Main {
static boolean exists(int[] ints, int k) {
boolean flag = false;
for (int i = 0; i < ints.length; i ) {
if (ints[i] == k) {
flag = true;
return flag;
} else {
continue;
}
}
return flag;
}
public static void main(String []args){
int[] ints = {-9, 14, 37, 102};
System.out.println(Main.exists(ints,9)); // true
System.out.println(Main.exists(ints, 102));
}
}
but after submitted the code, this is the result The solution works with a 'small' array
The solution works with an empty array
The solution Doesn't work in a reasonable time with one million items, So ,why it is not working if anyone can clarify that
The solution works if k is the first element in the array
The solution doesn't use the J2SE API to perform the binary search
CodePudding user response：
Your code uses an inefficient algorithm.
Modern CPUs and OSes are incredibly complicated and do vast amounts of bizarre optimizations. Thus, 'save some CPU cycles' is not something you can meaningfully reason about anymore. So let's objectify that statement into something that is useful:
The exercise wants you to find the algorithmically least complex algorithm for the task.
"Algorithmic complexity" is best thought of as follows: Define some variables. Let's say: The size of the input array. Let's call it N.
Now pick a bunch of numbers for N, run your algorithm a few times averaging the runtime. Then chart this. On the x-axis is N. On the y-axis is how long it took.
In other words, make some lists of size 10 and run the algorithm a bunch of times. Then go for size 20, size 30, size 40, and so on. A chart rolls out. At the beginning, for low N, it'll be all over the place, wildly different numbers. Your CPU is busy doing other things and who knows what - all sorts of esoteric factors (literally what song is playing on your music player, that kind of irrelevant stuff) control how long things take. But eventually, for a large enough N, you'll see a pattern - the line starts coalescing, the algorithmic complexity takes over.
At that point, the line (from there on out - so, looking to the 'right', to larger N) looks like a known graph. It may look like y = x - i.e. a straight line at an angle. Or like y = x^2. Or something complicated like y = x^3 x!.
That is called the big-O number of your algorithm.
Your algorithm has O(n) performance. In other words, an angled line: If 10,000 items takes 5 milliseconds to process, than 20,000 items will take 10, and 40,000 items will take 20.
There is an O(log n) algorithm available instead. In other words, a line that becomes nearly entirely horizontal over time. If 10,000 items take 5 milliseconds, then 100,000 takes 10 milliseconds, and a million takes 20. Make N large enough and the algorithmically simpler one will trounce the other one, regardless of how many optimizations the algorithmically more complex one has. Because math says it has to be that way.
Hence trivially no amount of OS, JVM, and hardware optimizations could ever make an O(n^2) algorithm be faster than an O(n) one for a large enough N.
So let's figure out this O(log n) algorithm.
Imagine a phone book. I ask you to look up Mr. Smith.
You could open to page 1 and start reading. That's what your algorithm does. On average you have to read through half of the entire phonebook.
Here's another algorithm: Instead, turn to the middle of the book. Check the name. Is that name 'lower' or 'higher' than Smith? If it's lower, tear the top half of the phone book and toss it in the garbage. If it's higher, tear the bottom half off and get rid of that.
Then repeat: Pick the middle of the new (half-sized) phonebook. Keep tearing out half of that book until only one name remains. That's your match.
This is algorithmically less complicated: With a single lookup you eliminate half of the phonebook. Got a million entries in that phonebook? one lookup eliminates HALF of all names it could be.
In 20 lookups, you could get an answer even if the phonebook has 2^20 = 1 million items. Got 21 lookups? Then you can deal with 2 million items.
The crucial piece of information is that your input is sorted. It's like the phone book! You can apply the same algorithm! Pick a start and end, then look at the middle. Is it your answer? great, return true;. Is it not? If lower, then start now becomes the middle, and start the algorithm again. Is it higher? Then end now becomes the middle. Is start and end identical? Then return false.
That's the algorithm they want you to write. It's called "binary search". Wikipedia has a page on it, lots of web tutorials cover the notion. But it's good to know why binary search is faster.
NB: Moore's Law, an observation that computers get faster over time, more or less limits technical improvement at O(n^2). In other words, any algorithm whose algorithmic complexity is more complicated than O(n^2) is utterly safe - no amount of technological advancement will ever mean that an algorithm that cannot reasonably be run today can run in a flash on the hardware of tomorrow. Anything that is less complicated can just wait for technology to become faster. In that sense, anything more complex than O(n^2) will take literally quadrillions of years for large enough N, and always will. That's why we say 'this crypto algorithm is safe' - because it's algorithmically significantly more complicated than O(n^2) so the Apple M99 chip released in 2086 still can't crack anything unless you give it quadrillions of years. Perhaps one day quantum tech leapfrogs this entire notion, but that's a bit too out there for an SO answer :)
CodePudding user response：
You need to take advantage of the fact the integers are presented in a sorted order by implementing a binary search, which can be boiled down to repeatedly looking at the middle element of the array to check if its bigger or lesser than the given number, and then recursively repeating the process the left or right half of the array. This algorithm will use significantly less array access operations given a large array.
Here's a more detailed explanation: https://en.wikipedia.org/wiki/Binary_search_algorithm
The sample code:
boolean binsearch(int[] ints, int k) {
return binsearchRange(ints, k, 0, ints.length - 1);
}
boolean binsearchRange(int[] ints, int search, int left, int right) {
if (right - left <= 1) {
return (ints[left] == search || ints[right] == search);
}
int middle = (left right) / 2;
if (ints[middle] == search) {
return true;
}
if (ints[middle] > search) {
return binsearchRange(ints, search, left, middle - 1);
}
return binsearchRange(ints, search, middle 1, right);
}