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.length-1;
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;
}
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();
}
}
//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;
}
Repeddieroonie, Member Technical Staff at BMO Harris Bank
I am Eddie, documentation specialist , responsible for creating, updating and maintaining the integrity of organizational instructional documentation. I also love ...
Repsarciasonda, Associate at ABC TECH SUPPORT
Computer forensics investigators, also known as computer forensics specialists, computer forensics examiners, government , accounting firms, law firms, banks, and software ...
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