engzizo
BAN USERthis should solve it
int finder(int arr[], int start, int end, int val)
{
int mid=(end-start)/2+start;
if(start==end)
{
if(arr[start]==val)
return start;
else
return -1;
}
//is first half sorted?
if(arr[start]<= arr[mid]){
if(arr[start]<= val && val<=arr[mid])
return finder(arr, start, mid, val);
else{
int x = finder(arr, mid+1, end, val);
if(x>-1)
return x;
else
return finder(arr, start, mid, val);
}
}
else //the second half of array is sorted
{
if(arr[mid+1]<= val && val<=arr[end])
return finder(arr, mid+1, end, val);
else{
int x = finder(arr, start, mid, val);
if(x>-1)
return x;
else
return finder(arr, mid+1, end, val);
}
}
}
Just a little simpler to read
public void printDiag(char[] x){
int start = 0;
int inc =1;
while(start<x.length){
printLine(x, start, inc);
System.out.println();
start+= ++inc;
}
}
private void printLine(char[] x, int start, int inc){
while(start<x.length){
System.out.print(x[start] +"\t");
start += inc++;
}
}
char current;
int currentCount;
int currentStart;
char previous;
int previousCount;
int previousStart;
int contiguousStart;
int contiguousLength;
public void find(char[] arr){
current = arr[0];
for(int i=0; i<arr.length; i++){
if(arr[i] != current || i==arr.length-1){
if(previous != '\0'){
int length = 2 * Math.min(currentCount, previousCount);
if(length > contiguousLength){
contiguousLength = length;
if(previousCount <= currentCount){
contiguousStart = previousStart;
}else{
contiguousStart = currentStart - currentCount -1;
}
}
}
previous = current;
previousCount = currentCount;
previousStart = currentStart;
current = arr[i];
currentCount=1;
currentStart = i;
}else{
currentCount++;
}
}
}
the binary search u implemented is not O(log n).. yes, it splits the array in half but you will search both sides so it is still O(n)
- engzizo November 25, 2014