1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Why does binary search work this way?

  1. Nov 21, 2016 #1
    1. The problem statement, all variables and given/known data
    Code (Java):

    public class BinarySearch {
        public static boolean search(int[] array, int searchedValue) {
            int beginning = 0;
            int end = array.length - 1;

            while (beginning <= end) {
                int middle = (beginning + end) / 2;
                if (array[middle] == searchedValue) {
                    return true;
                }
                else if (array[middle] > searchedValue) {
                    end = middle - 1;
                }
                else if (array[middle] < searchedValue) {
                    beginning = middle + 1;
                }
             
            }
            return false;
        }
    }
    /*
    middle = 3
    array[3] > -3
    end = 3;
    middle = 0 + 3 /2 = 1.5 so 1
    array[1]>-3
    end = 1
    middle = 0 + 1 /2 = 0
    array[0] == -3
    return true
    */

     
    2. Relevant equations


    3. The attempt at a solution
    The following code is meant to search if an array has a searched value(from the user). My question is why do we need to do this:
    end = middle - 1
    and
    beginning = middle + 1

    I noticed that when I input some values without the + and - 1 in the algorithm that it still works, to a varying degree. Why is this?
     
  2. jcsd
  3. Nov 21, 2016 #2

    jbriggs444

    User Avatar
    Science Advisor

    Think about what one iteration through the loop will accomplish. Written down in words:

    Each iteration will either: 1) Find the searched-for value or 2) Reduce the remaining range to be searched.

    Can you think of a way that 2) could fail without the -1 and +1? Hint: integer division.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Why does binary search work this way?
  1. Binary Search tree (Replies: 5)

Loading...