CODEWITHSUNDEEP
javaarrayselementbinary-search
David Arriaga
David Arriaga

Reputation: 69

Binary search not return true in first iteration of while loop when target == list[mid]

I thought I was an expert of binary search because i can do it linear, recursive and iterative but i cant even get this to work in java

so if i set my target variable to equal the mid point, my if statement skips over that and moves on to else if 

public static void main(String[] args) {
        int[] list = { 11, 22, 33, 44, 55, 66, 77, 88, 99 };
        int target = 44;
        System.out.print(BinarySearchIterarive(list, target));

    }

    public static boolean BinarySearchIterarive(int[] list, int target) {
        int high = list.length - 1;
        int low = 0;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (target == list[mid]) {
                      return true;
            } else if (target < list[mid]) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }

        }
        return false;
    }
}

It just skips over my if statement of 

if (target ==list[mid])

when list[mid]is 44

Upvotes: 1

Views: 107

Answers (1)

Rakib
Rakib

Reputation: 145

Let's do a simple tracing here.

11 | 22 | 33 | 44 | 55 | 66 | 77 | 88 | 99

Target: 44

First step: high = 8, low = 0

low <= high

Enters the loop: mid = 4, list[4] = 55

Target < list[mid]
high = 3, low = 0

Second step: high = 3, low = 0

low <= high

Enters the loop: mid = 1, list[1] = 22 Here as mid is an integer fraction part is ignored during calculation

Target > list[mid]

Hence, low = 2, high = 3

Third Step: high = 3, low = 2 Again, low <= high, Enters loop: mid = 2, list[2] = 33

Target > list[mid]

Hence, low = 3, high = 3

Final Step:

low == high

Enters loop: mid = 3, list[3] = 44

Target = list[mid]
returns true

Upvotes: 1

Related Questions