Java Programming 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

collection sorted

Binary search: reduces the number of iterations to search the particular element (only 3 iterations in below example).

linear search

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 Programming 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 {
			System.out.println("Search key is not found in Array of Integers!");
		}
	}
}
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
Search key is not found in Array of Integers!

Java Programming 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 {
			System.out.println("Search key is not found in Array of Integers!");
		}
	}
}
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 Programming 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 {
			System.out.println("Search key is not found in Array of Integers!");
		}
	}
}

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
Java Programming Examples

GCD and Rational Number Java Program

Java Queue Program using exception

Java Stack Program using exception

Addition of three integers java program

Biggest of three integers java program

Fibonacci numbers java program

Arithmetic Operations Menu java program

Second Smallest Element In Array Java Program

Transpose Of A Matrix Java Program

Java Program to Display triangle of stars (*)

Java Programming Prints Product Tables

Java Program to Display triangle of numbers

Java Programming Gets Current Date

Java Programming Finds Character Vowel or Consonent

Java Programming HCF and LCM Computation

Java Programming Sum of Command Line Integer Arguments

Java Programming Multiplication of Command Line Integer Arguments

Java Programming Multiplication of Command Line Floating Point Numeric Arguments

Java Programming String Contains or Not

Java Programming Gets Grade Description using Switch

Java Programming CSV File Reader

Java Programming Character Frequency Count in String using for each

Java Programming Finds Min from Integer Array by Passing Array to Method

Java Programming Linear Search

Java Programming Binary Search

Java Programming Ternary Search

Java Programming Generates Range of Numbers

Java Programming Generates Range of Characters

Java Programming Computes Square Root Value

Java Programming Checks Number is Positive or Negative

Java Programming Checks Number is Odd or Even

Java Programming Computes Plot Area

Java Programming Convert Number of Days into Years

Java Programming Checks a Year is Leap Year, Century Year or Not

Java Programming Checks a Character is Digit, Letter or neither digit nor letter

Java Programming Checks a Number is Palindrome or not

Java Programming Sum of Two Matrix

Java Programming Power Computation

Java Programming Checks Number is an Armstrong Number or not

Java Programming Temperature Unit Conversions

Java Programming Generates Random Numbers in Specified Range

Java Programming Computes Sum of Digits and Product of Digits

Java Programming Computes Reverse Number

Java Programming Computes Factorial Value

Java Programming Checks Prime Number or not

Java Programming Computes Harmonic Series

Java Programming Generates Floyd's Triangle

Java Programming Reverses String

Java Programming Checks Palindrome String or not

Java Programming Opens Notepad

Java Programming Searches String using RegEx Pattern

Java Programming Searches Word in String

Java Programming Gets System Environment Variables

Java Programming Gets IP Address of Server Name

Java Programming Arrays Sort and Reverse using sort method

Java Programming Bubble Sorting

Java Programming Selection Sorting

Java Programming Insertion Sorting

Java Programming Merge Sorting

Java Programming Quick Sorting

Java Programming Counting Sort

Java Programming Radix Sorting

Java Programming Sorting Array of Strings

Java Programming String Characters Sorting

Java Programming Sum of First N Numbers

Java Programming Product of First N Numbers

Privacy Policy  |  Copyright@2017 - All Rights Reserved.  |  Contact us   |  Report website issues in Github   |  Facebook page   |  Google+ page

Email Facebook Google LinkedIn Twitter
^