## Wednesday, February 14, 2024

### Binary Search Program in Java

In this post we’ll see how to write Binary search program in Java. Binary search is a divide and conquer algorithm which reduces the range of search by half in each iteration, thus making it more efficient than the Linear search.

### How does Binary search work

One of the prerequisite for the Binary search is that the input array should be sorted.

In each iteration searched element is compared with the middle element of the array. If searched element is less than the middle element of the array that means the searched element should be in between the start element to middle element of the array as the array is sorted.

In the next iteration search is done with in the sub-array start to middle (0 to (n/2-1)) or with in the sub-array ((n/2+1) to end) if searched element is greater than the middle element.

This process of division and searching continues unless the element is found or the length of the sub-array becomes 0 which means searched element is not found in the array.

Following image shows the process of division in each iteration

### Binary search Java program

Java program for Binary search can be written in both recursive and iterative ways. We’ll see both of these solutions here.

Binary search in Java – Iterative program

```public class BinarySearch {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int[] arr = {12, 23, 10, 34, 55, 4, 68, 3, 73, 99};
Arrays.sort(arr);
System.out.println("sorted array- " + Arrays.toString(arr));
System.out.println("Enter value to search: ");
int searchElement = sc.nextInt();
int index = binarySearch(arr, 0, arr.length-1, searchElement);
if(index != -1){
System.out.println("Searched item " + arr[index] + " found at index "+index);
}else{
System.out.println("Searched item " + searchElement + " not found in the array");
}
}

private static int binarySearch(int[] arr, int start, int end, int searchElement){
while(start <= end){
int middle = (start+end)/2;
System.out.println("start- " + start + " end " + end + " middle- " + middle);
// element found
if(searchElement == arr[middle]){
return middle;
}
// left half
if(searchElement < arr[middle]){
end = middle - 1;
}else{
// right half
start = middle + 1;
}
}
return -1;
}
}
```

Output

```sorted array- [3, 4, 10, 12, 23, 34, 55, 68, 73, 99]
Enter value to search:
34
start- 0 end 9 middle- 4
start- 5 end 9 middle- 7
start- 5 end 6 middle- 5
Searched item 34 found at index 5
```

Binary search in Java – Recursive program

```public class BinarySearch {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int[] arr = {12, 23, 10, 34, 55, 4, 68, 3, 73, 99};
Arrays.sort(arr);
System.out.println("sorted array- " + Arrays.toString(arr));
System.out.println("Enter value to search: ");
int searchElement = sc.nextInt();
int index = binarySearch(arr, 0, arr.length-1, searchElement);
if(index != -1){
System.out.println("Searched item " + arr[index] + " found at index "+index);
}else{
System.out.println("Searched item " + searchElement + " not found in the array");
}
}

private static int binarySearch(int[] arr, int start, int end, int searchElement){
// exit condition
if(start > end){
return -1;
}
int middle = (start+end)/2;
System.out.println("start- " + start + " end " + end + " middle- " + middle);
// element found
if(searchElement == arr[middle]){
return middle;
}
// left half
if(searchElement < arr[middle]){
return binarySearch(arr, start, middle-1, searchElement);
}else{
// right half
return binarySearch(arr, middle+1, end, searchElement);
}
}
}
```

Output

```sorted array- [3, 4, 10, 12, 23, 34, 55, 68, 73, 99]
Enter value to search:
55
start- 0 end 9 middle- 4
start- 5 end 9 middle- 7
start- 5 end 6 middle- 5
start- 6 end 6 middle- 6
Searched item 55 found at index 6
```

### Performance of Binary search

Time complexity of Binary search is O(logn).

Space complexity of Binary search is O(1) as no auxiliary space is needed. Though recursive solution will have method stacks for each recursive call making the space complexity as O(logn).

That's all for this topic Binary Search Program in Java. If you have any doubt or any suggestions to make please drop a comment. Thanks!