boyjemmy
BAN USEROnly one pass of binary search without knowing k
public static int binarySearch(int[] arr, int value){
int low =0;
int high = arr.length1;
while(low <= high){
int mid = (low + high)/2;
if(arr[mid] == value){
return mid;
}else if(arr[mid] > value){
if(arr[high] > arr[mid]  arr[high] < value){
high = mid 1;
}else{
low = mid + 1;
}
}else{
if(arr[low] <= arr[mid]  arr[low] > value){
low = mid + 1;
}else{
high = mid  1;
}
}
}
return 1;
}

boyjemmy
July 01, 2010 One code example
import java.util.*;
public class test2 implements Runnable{
String s1 ;
String s2 ;
public test2(String s1, String s2){
this.s1 = s1;
this.s2 = s2;
}
public void printOne() throws Exception{
synchronized(s1){
Thread.sleep(10000);
synchronized(s2){
System.out.println (s1 + s2);
}
}
}
public void printTwo() throws Exception{
synchronized(s2){
Thread.sleep(10000);
synchronized(s1){
System.out.println (s1 + s2);
}
}
}
public void run() {
try{
printOne();
}catch(Exception e){
}
}
public static void main(String[] args) throws Exception{
String s1 = "dead";
String s2 = "lock";
test2 t = new test2(s1, s2);
new Thread(t).start();
t.printTwo();
}
}

boyjemmy
July 01, 2010 //The worst case time complexity for this approach is O(mlogn), so it suits when m << n
//When return 1 means no row has true value
public int maxtrueRowBS(boolean val[][], int m, int n){
int row = 1, i=0, j=0;
while(i < m && j < n){
//BS finds the first false in row i of val starting col j
//If no false value found, return 1;
int k = BS(val, i, j);
if(k == 1) {row = i; break;}
if(k > j) { j = k; row = i;}
i++;
}
return row;
}
//Following apporach time complexity is o(n), binary search can be used to further optimize it
//When return 1 means no row has true value
public int maxtrueRow(boolean val[][], int m, int n){
int row = 1, i=0, j=0;
while(i < m && j < n){
if(val[i][j]){
j++;
row = i;
}else{
i++;
}
}
return row;
}
Open Chat in New Window
This may not work for following case
 boyjemmy July 01, 20103 3 3 4 5 1 2 3 3 3 3 3 3 3 3 3 3 3 3
and if you change a[mid]< a[start] to a[mid] <= a[start], it may not work for following case
3 3 3 3 3 3 3 3 3 3 3 3 3 4 5 1 2 3 3