Issues with Binary Search Algorithm

Question

I have an assignment to write a binary search that returns the first iteration of the value we are looking for. I've been doing some research online and my search looks a lot like what i'm finding but i'm having an issue. If I pass this code an array that looks like this {10,5,5,3,2} it find the 5 at in the middle(The first thing it checks) and then just returns it. But that is not the first iteration of the 5 it is the second. What am I doing wrong? Is this even possible?

Thanks in advance!

The code(I'm using Java):

public static int binarySearch(int[] arr, int v){
    int lo = 0;
    int hi = arr.length-1;
    while(lo <= hi){
        int middle = (lo+hi)/2;
        if(v == arr[middle]){
            return middle;
        }
        else
        {
            if(v < arr[middle]){
                lo = middle+1;
            }  
            else
            {
                hi = middle-1;
            }
        }
    }
    return -1;
}

For binary search to work, your array has to be sorted first. You find 5 at position 2 because it is the middle element in the first iteration and won't work finding other elements. To find the first occurrence is possible and it is called the lower_bound — thebenman
– thebenman, Commented Feb 25, 2019 at 3:33
There are two possible ways to fix it: 1) after a hit, continue the search on the left side to find possible other occurrences. 2) after a hit check the neighboring elements on the left one by one until you reach the first one. Option 2 should only be done if you know that duplicates don't occur often as it may degrade to O(n) effort. — Henry
– Henry, Commented Feb 25, 2019 at 5:32

Cătălin Frâncu · Accepted Answer · 2019-02-25 09:41:21Z

1

Here is a modified algorithm that works.

public static int binarySearch(int[] arr, int v) {
  int lo = -1;
  int hi = arr.length - 1;

  while (hi - lo > 1 ) {
    int middle = (lo + hi) / 2;
    if (arr[middle] > v) {
      lo = middle;
    } else {
      hi = middle;
    }
  }

  if (v == arr[hi]) {
    return hi;
  } else {
    return -1;
  }
}

The key points are:

The interval (lo, hi] is exclusive to the left, inclusive to the right.
At each step we throw away one half of the interval. We stop when we are down to one element. Attempts to terminate early offer only a minimal performance boost, while they often affect code legibility and/or introduce bugs.
When arr[middle] = v we assign hi = middle, thus throwing away the right half. This is safe to do because we don't care any occurrences of v past middle. We do care about arr[middle], which may or may not be the first occurrence, and it is for this reason that we made (lo, hi] inclusive to the right. If there are occurrences of v before middle, we will find them in subsequent iterations.
As a side note, the more natural definition [0, n) inclusive to the left, exclusive to the right, can be used to find the last occurrence of v.

In my experience, this inclusive-exclusive interval definition produces the shortest, clearest and most versatile code. People keep trying to improve on it, but they often get tangled up in corner cases.

answered Feb 25, 2019 at 9:41

Cătălin Frâncu

1,1991 gold badge9 silver badges15 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Luke Kelly Over a year ago

Correct me if i'm wrong but if you are looking for the value stored in index 0 this will not find it correct? Eventually it will check if arr[1] > v that will be false. Then it will set hi = 1. 1-0 = 1 which is not greater than 1 so it doesn't check the last index because the while loop returns false? To fix this you would have to change the while loop to be (hi-lo >=1).

Cătălin Frâncu Over a year ago

It does work; after checking arr[1] > v, it sets hi = 1 (lo is still -1). Then the last iteration sets middle = (1 + (-1)) / 2 = 0 and subsequently hi = 0. At this point hi - lo = 1 and the function returns hi, that is 0.

Luke Kelly Over a year ago

Oh when I did my calculations I had lo set to 0 like in my original code. My bad, thanks for the clarification.

Collectives™ on Stack Overflow

Issues with Binary Search Algorithm

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related