 Java Tutorial

Java Program for Binary Search

What is binary search ?

Binary search is used only on a sorted collection of elements.

Most commonly used techniques to solve problems.

Number of iterations can be reduced in binary search on the basis of the value that is being searched.

Example, consider sorted collection of elements Binary search: reduces the number of iterations to search the particular element (only 3 iterations in below example). Binary Search Time complexity

Binary search performs the search operation on the other half in every steps. This results in a worst case time complexity of O(log2N), where N is the number of elements in the collection.

Note:

Below Java programs return the index of an array and index starts with 0, so if 4th element matches in the array returns 3.

Java Program for Binary Search using While loop

Reads array of integers as sorted order and finds the search key in an array of integers.

```import java.util.*;

class BinarySearchTest {
// Binary search method which search key in the array of integers
// using while loop
static int binarySearch(int[] numbers, int searchKey){
int lowIndex = 0;
int highIndex = numbers.length-1;

while(lowIndex <= highIndex){
int midIndex = (lowIndex + highIndex)/2;
if (numbers[midIndex] < searchKey){
lowIndex = midIndex + 1;
}
else if (numbers[midIndex] > searchKey){
highIndex = midIndex - 1;
}
else{
return midIndex;
}
}

return -1;
}

// Gets the Array of Integers
static int[] getNumbers(Scanner sc){
int[] numbers;
System.out.print("Enter Number of Elements: ");
int count = sc.nextInt();
numbers = new int[count];
System.out.println();
System.out.println("Enter Array Numbers:");
for (int i=0;i<count;i++){
numbers[i]=sc.nextInt();
}
return numbers;
}
public static void main(String[] args){
int[] numbers;
Scanner sc = new Scanner(System.in);
numbers = getNumbers(sc);
System.out.println();
System.out.print("Enter Search Key: ");
int searchKey = sc.nextInt();
sc.close();
int index = binarySearch(numbers, searchKey);
// Prints the result, index -1 indicates that key is not found,
//otherwise index location where key is found in array of integers.
if (index >= 0){
System.out.println("Search key index in Array of Integers: "+index);
} else {
}
}
}
```
Output:
```D:\Java_Programs>javac BinarySearchTest.java
D:\Java_Programs>java BinarySearchTest
Enter Number of Elements: 5

Enter Array Numbers:
1
2
3
4
5

Enter Search Key: 3
Search key index in Array of Integers: 2

D:\Java_Programs>javac BinarySearchTest.java
D:\Java_Programs>java BinarySearchTest
Enter Number of Elements: 5

Enter Array Numbers:
1
2
3
4
5

Enter Search Key: 4
Search key index in Array of Integers: 3

D:\Java_Programs>javac BinarySearchTest.java
D:\Java_Programs>java BinarySearchTest
Enter Number of Elements: 5

Enter Array Numbers:
1
2
3
4
5

Enter Search Key: 6
```

Java Program for Binary Search using for loop

Reads array of integers as sorted order and finds the search key in an array of integers using for loop.

```import java.util.*;

class BinarySearchTest {
// Binary search method which search key in the array of integers
// using for loop
static int binarySearch(int[] numbers, int searchKey){

for(int lowIndex = 0, highIndex = numbers.length-1;(lowIndex <= highIndex);){
int midIndex = (lowIndex + highIndex)/2;
if (numbers[midIndex] < searchKey){
lowIndex = midIndex + 1;
}
else if (numbers[midIndex] > searchKey){
highIndex = midIndex - 1;
}
else{
return midIndex;
}
}

return -1;
}

// Gets the Array of Integers
static int[] getNumbers(Scanner sc){
int[] numbers;
System.out.print("Enter Number of Elements: ");
int count = sc.nextInt();
numbers = new int[count];
System.out.println();
System.out.println("Enter Array Numbers:");
for (int i=0;i<count;i++){
numbers[i]=sc.nextInt();
}
return numbers;
}
public static void main(String[] args){
int[] numbers;
Scanner sc = new Scanner(System.in);
numbers = getNumbers(sc);
System.out.println();
System.out.print("Enter Search Key: ");
int searchKey = sc.nextInt();
sc.close();
int index = binarySearch(numbers, searchKey);
// Prints the result, index -1 indicates that key is not found,
//otherwise index location where key is found in array of integers.
if (index >= 0){
System.out.println("Search key index in Array of Integers: "+index);
} else {
}
}
}
```
Output:
```D:\Java_Programs>javac BinarySearchTest.java
D:\Java_Programs>java BinarySearchTest
Enter Number of Elements: 5

Enter Array Numbers:
1
2
3
4
5

Enter Search Key: 5
Search key index in Array of Integers: 4
```

Java Program for Binary Search using Recursive Method

```import java.util.*;

class BinarySearchTest {
// Binary search method which search key in the array of integers
// using recursive method
static int binarySearch(int[] numbers, int searchKey, int lowIndex, int highIndex){

if(lowIndex <= highIndex){
int midIndex = (lowIndex + highIndex)/2;
if (numbers[midIndex] < searchKey){
lowIndex = midIndex + 1;
}
else if (numbers[midIndex] > searchKey){
highIndex = midIndex - 1;
}
else{
return midIndex;
}
return binarySearch(numbers, searchKey, lowIndex, highIndex);
}

return -1;
}

// Gets the Array of Integers
static int[] getNumbers(Scanner sc){
int[] numbers;
System.out.print("Enter Number of Elements: ");
int count = sc.nextInt();
numbers = new int[count];
System.out.println();
System.out.println("Enter Array Numbers:");
for (int i=0;i<count;i++){
numbers[i]=sc.nextInt();
}
return numbers;
}
public static void main(String[] args){
int[] numbers;
Scanner sc = new Scanner(System.in);
numbers = getNumbers(sc);
System.out.println();
System.out.print("Enter Search Key: ");
int searchKey = sc.nextInt();
sc.close();
int lowIndex = 0;
int highIndex = numbers.length - 1;
int index = binarySearch(numbers, searchKey, lowIndex, highIndex);
// Prints the result, index -1 indicates that key is not found,
//otherwise index location where key is found in array of integers.
if (index >= 0){
System.out.println("Search key index in Array of Integers: "+index);
} else {
}
}
}

```
Output:
```D:\Java_Programs>javac BinarySearchTest.java
D:\Java_Programs>java BinarySearchTest
Enter Number of Elements: 5

Enter Array Numbers:
1
2
3
4
5

Enter Search Key: 4
Search key index in Array of Integers: 3
```     