Sorting Challenges Comments
Comments
-
The code usually runs in a few seconds (and doesn't display quotes), but sometimes it needs to fall back to a different server.
-
I have implemented binary search by recursion.
Here is my code:static void doStuff(int[] ar){
//your code here
int low = 0;
int high = ar.length-1;int record = 0; for(int i=0; i<ar.length; i++) { record = record + find(low,high,ar,i); } if(record == ar.length*(-1)) System.out.print(-1);}
static int find(int low,int high,int[] ar,int i){
int mid = (low+high)/2;if (high<low) { return -1; } if (ar[i] > ar[mid]) { return find(mid+1,high,ar,i); } else if (ar[i] < ar[mid]) { return find(low,mid-1,ar,i); } else { System.out.print(ar[i] + " "); return 0; }}
I can't figure out what wrong with it.
Could anyone can give me some advices? -
曾國峻 I needed to keep track of the index and pass it back up the recursion to solve it. Because each time the binary search needed to look at the > side of the array, the index forgets about the lower half of the array. Here is my solution in Ruby:
def index_match(ar, index=0)
mid = ar.length/2 actual_index = mid + index if ar[mid] == actual_index return actual_index elsif ar.length == 1 return -1 elsif ar[mid] < mid index_match(ar[(mid + 1)..-1], actual_index + 1) # here is where we check the > side of the array, and need to pass the index to keep track of it (or it keeps returning to 0) else # ar[mid] > mid index_match(ar[0..(mid - 1)], index) endend
-
Better to solve without recursion. maybe can be a bit more elegant, but works.
int start = 0; int end = ar.length-1; int i = start + ((end - start) / 2);while (start < end && ar[i] != i){ if(ar[i] > i){ if(end == i){ break; } end = i; } else { if(start == i){ break; } start = i; } i = start + ((end - start) / 2); } if(ar[i] == i){ System.out.println(i); } else { System.out.println(-1); } -
If you're looking for code to get started, this Java code converts the input into Tuples, and added a helpful compareTo method to the Tuples.
-
Am I supposed to change the boilerplate code? Can I pass two arrays to doStuff or do I have to combine both lists in one array?
-
@Kendall, you can modify the method however you want. I created boilerplate that does that here: http://www.learneroo.com/user_answers/6879587411
-
The two arrays don't appear to match up at all on the second run. I printed out the first 10 and they didn't match. What am I missing? Thanks!
-
@Kendall, the numbers are in different orders in each list. You need to find the extra numbers in list B, preferably without sorting the lists. I added another test case to make it clearer.
-
Got it, I interpreted identical lists to mean identical orders. Thanks!
Panashe Fundira
Jun 19, 11:03 AMI like the quotes :)
Just wish it would run code a little faster though