Skip to content

Instantly share code, notes, and snippets.

@jingz8804
Last active November 29, 2017 07:56
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jingz8804/9349194 to your computer and use it in GitHub Desktop.
Save jingz8804/9349194 to your computer and use it in GitHub Desktop.
Search an integer in a bitonic array (holding distinct integers)
public class BitonicArraySearch{
private int[] numbers;
private int len;
private int turningPointIndex = -1;
public BitonicArraySearch(int[] numbers){
this.numbers = numbers;
len = numbers.length;
}
private boolean binarySearch(int target, int low, int high){
int mid = -1;
while(low <= high){
mid = (low + high) / 2;
if (target == numbers[mid]){
return true;
}else if(target > numbers[mid]){
low = mid + 1;
}else{
high = mid - 1;
}
}
return false;
}
private boolean binarySearchReversed(int target, int low, int high){
int mid = -1;
while(low <= high){
mid = (low + high) / 2;
if(target == numbers[mid]) return true;
else if(target > numbers[mid]) high = mid - 1;
else low = mid + 1;
}
return false;
}
private int binarySearchForTurningPoint(){
int mid = -1;
while (low <= high){
mid = (low + high) / 2;
if (mid == 0 || mid == len - 1) return mid; // otherwise we have an array index overflow problem
if ((numbers[mid - 1] < numbers[mid]) && (numbers[mid] > numbers[mid + 1])) return mid;
if ((numbers[mid - 1] < numbers[mid]) && (numbers[mid] < numbers[mid + 1])){
low = mid + 1;
}
if ((numbers[mid - 1] > numbers[mid]) && (numbers[mid] > numbers[mid + 1])){
high = mid - 1;
}
}
return mid;
}
public boolean search(int target){
if (turningPointIndex < 0){
turningPointIndex = binarySearchForTurningPoint();
}
if (binarySearch(target, 0, turningPointIndex)) return true;
if (binarySearchReversed(target, turningPointIndex + 1, len-1)) return true;
return false;
}
}
@ptyshevs
Copy link

ptyshevs commented Nov 29, 2017

@gborn
It won't segfault or anything, but the result depends on the arrangement of duplicates w.r.t. other elements. In other words, what index will be returned depends on:

  1. in case the bitonic point has duplicates, on which bitonic element the split happens to be.
  2. where the split happens to be in a subsequence of duplicates. To illustrate:
int a[7] = {1, 2, 2, 4, 4, 5, 3};
bitonic_search(a, 0, 7 - 1, 4); // returns 3, left-most element of a duplicates subsequence.
int b[7] = {4, 4, 5, 5, 5, 5, 3};
bitonic_search(b, 0, 7 - 1, 4); // returns 1, which is the duplicate on the "right"

Be heedful, that if sequence consists only of duplicates ({1, 1, ..., 1}), it is not bitonic.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment