Binary Search - Java

Question

Question :

Write a java program to search an element in a sorted list and output the position using binary

search algorithm. Use separate function search (element, array) to search an element.

Format of code given in my notes :

1.Set BEG = LB, END = UB and MID = INT([BEG+END]/2)

2.Repeat step 3 and 4 while BEG <= END and ARR[MID] != TARGET

3.IF TARGET < ARR[MID] then:

Set END = MID 1

Else:

Set BEG = MID+1

4.Set MID = INT(BEG+END)/2

5.IF ARR[MID] = TARGET then:

Set LOC = MID

Else:

Set LOC = NULL

6. Exit.

My code :

public class binarySearch{

public static int search(int target, int arr[]){

int beg = 1;

int end = arr.length;

int mid = (beg+end)/2;

while( (beg<=end) && (arr[mid] != target) ) {

if(target < arr[mid])

end = mid-1;

else

beg = mid+1;

mid = (beg+end)/2;

}

if(arr[mid] == target)

return mid;

else

return -1;

}

public static void main(String []args){

int array[] = {2, 8, 10, 17, 32, 34, 50, 57, 61};

int element = 57;

int result = search(element, array);

if(result == -1)

System.out.println("Element is not present in array");

else

System.out.println("Element is present at index : "+result);

}

}

When I enter an element larger than the highest element in the array ( say 69), to be searched it displays following error message :

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 9

at binarySearch.search(binarySearch.java:11)

at binarySearch.main(binarySearch.java:37)

Can anyone correct me and provide a correct code?

Answer 1

Yes, Kevin is correct...

The max index is arr.length-1

I tested all four cases:

(1) item is at the front 2

(2) item is at the back 61

(3) item is somewhere in between 57

(4) item is not there at all 42

it works

good job!!!

Answer 2

I'm thinking that your second line should be: int end = arr.length - 1;

The highest index in the array is arr.length - 1, so index arr.length is out of bounds.

Your code eventually tries to do arr[mid] when mid equals arr.length.

Your notes has it like this:

Set BEG = LB, END = UB

The lower bound and upper bound are both inclusive.

Your current code has the lower bound inclusive and the upper bound exclusive.