# Modified Binary Search java

So I'm running into a huge road block....maybe it's just because my logic is not there but I can't seem to figure this out on my own.

I'm trying to modify BinarySearch so that it will obtain two indexes.

First index is the farthest left index of a number given, x, and the farthest right. If the number doesn't exist then it produces [-1,-1].

Anyways. I have been trying to modify the BinarySearch and can't seem to get it working. Any pointers would be greatly appreciated.

public static Pair BinarySearchDup(int[] A, int x, int low, int high){
int mid = (low + high) / 2;
int left = -1, right = -1;
while(low <= high){
mid = (low + high) / 2;
if(A[mid] == x){
int newMid = mid;
//check left
if(left == -1){
left = mid;
return BinarySearchDup(A, x, low, mid - 1);
}
else if(right == -1){
right = mid;
return BinarySearchDup(A, x, newMid + 1, high);
}
return new Pair(left, right);
}
else if(A[mid] < x)
return BinarySearchDup(A, x, mid + 1, high);
else// (A[mid] > x)
return BinarySearchDup(A, x, low, mid - 1);
}
//if there are no matches of the number then it returns -1
return new Pair(-1, -1);
}
-

To solve this problem:

I'm trying to modify BinarySearch so that it will obtain two indexes. First index is the farthest left index of a number given, x, and the farthest right. If the number doesn't exist then it produces [-1,-1].

I would do this:

1) Do a binary search, except instead of considering the target a match and ending right away, consider it to be larger than your target (e.g. you search left of it). When this search ends, it'll either be on the leftmost instance of target, one left (depending on how it's coded - in this case just check one right) or it will be confirmed not to exist.

2) Do a binary search like in 1) except consider target smaller than your target. This will, in a similar way, find the rightmost instance of your target.

This gives you O(logN) complexity. Petar Ivanov's idea of "Can't you just use normal binary search and then simply go back and forth from the found index until you get the whole range?" can be as bad as O(N) if there is a huge number of duplicates in the array. However, if the expected duplicate count (or expected array size) is small, then Petar Ivanov's idea is far simpler to code since you don't have to remake binary search with changed logic.

-
Thanks, but I just talked to my teacher and turns out that I was doing it wrong. I was supposed to modify the iterative version of BS....which makes things a lot easier! –  kevorski Apr 8 '13 at 17:46
@Patashu I didn't get your answer. Can you explain me with example? How you got into O(logN) complexity? But first please explain how your methos works? –  Jemish Patel Sep 12 '13 at 21:05

I am not sure I understand your idea, but here is why it doesn't work:

public static Pair BinarySearchDup(int[] A, int x, int low, int high){
int mid = (low + high) / 2;
if(low <= high){
if(A[mid] == x)
return BinarySearchDup(A, x, low, mid - 1);
else if(A[mid] < x)
return BinarySearchDup(A, x, mid + 1, high);
else// (A[mid] > x)
return BinarySearchDup(A, x, low, mid - 1);
}

return new Pair(-1, -1);
}

Indeed, if you enter the while loop, you always return, so there is never more than one iteration. Also if the value at mid is x then since left is -1 you always enter this if clause. Alternatively if you don't enter the while loop you just return (-1, -1). Hope this helps.

EDIT: Can't you just use normal binary search and then simply go back and forth from the found index until you get the whole range?

-
So I'm supposed to be using BinarySearch to traverse through an array and then when it finds x it will search left and right to see if there are any other x's in the array. If there are any other x's it will then display the index and the farthest left and farthest right. So the idea is that it takes in a txt file with 2 2 5 6 8 10 10 10 10 11 21 25 26 what it will display is [5,8] if the x was 10 @PetarIvanov –  kevorski Apr 8 '13 at 2:05
{"found_math": false, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}