- Given sorted integer array in java.
- Find or search element/integer in an array using binary search algorithm (with example).
- Binary search is a divide and conquer algorithm.
- Binary search algorithm is used to find element in sorted arrays.
- We have already discussed about find element in a sorted integer array using binary search algorithm(recursive).
- We had discussed in detail about binary search algorithm using java.
- Recursive post is kind of prerequisite for current post.
- Arrays class in java also has predefined binary search function.
- We have demonstrated its sample code as follows.
int arr[] = {10,20,30,40,50,60,70,80,90,100};
System.out.println(Arrays.binarySearch(arr, 70));
//Output is: 6
1. Find/search element in sorted integer array in java (binary search algorithm)
package org.learn.arrays;
import java.util.Arrays;
public class BinarySearchIterative {
public static void main(String[] args) {
int arr[] = {10,20,30,40,50,60,70,80,90,100};
//low index
int low = 0;
//high index
int high = arr.length - 1;
int search = 70;
int result = binarySearch(arr, search, low, high);
if(result == -1) {
System.out.printf("1. Element %d not found in array",search);
} else {
System.out.printf("1. Element %d found at index : %d ",search,result);
}
System.out.println("");
search = 60;
result = binarySearch(arr, search, low, high);
if(result == -1) {
System.out.printf("2. Element %d not found in array",search);
} else {
System.out.printf("2. Element %d found at index : %d",search,result);
}
System.out.println("");
search = 110;
result = binarySearch(arr, search, low, high);
if(result == -1) {
System.out.printf("3. Element %d not found in array",search);
} else {
System.out.printf("3. Element %d found at index : %d",search,result);
}
System.out.println("");
}
private static int binarySearch(int[] arr, int value, int low, int high) {
while (low <= high) {
int middle = low + (high - low) / 2;
if (value < arr[middle]) { // search between low ---> middle
high = middle - 1;
} else if (value > arr[middle]) {
// search in upper half middle + 1 -----> high
// low to middle already covered in first case
// so start search from middle + 1 to high here...
low = middle + 1;
} else {
// value == arr[middle]
// yes we got the element in binary search tree
return middle;
}
}
return -1;
}
}
2. Find/search element in sorted integer array (java/binary search algorithm)
1. Element 70 found at index : 6
2. Element 60 found at index : 5
3. Element 110 not found in array