Java Tutorial
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 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.
Below Java programs return the index of an array and index starts with 0, so if 4th element matches in the array returns 3.
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!
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
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
Alternate way for recursive code with only if statements,
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 low, int high, int searchKey){ int midIndex = low+(high-1)/2; if(numbers[midIndex] == searchKey){ return midIndex; } if(numbers[midIndex] > searchKey){ return binarySearch(numbers, low, midIndex-1, searchKey); } return binarySearch(numbers, midIndex+1, high, searchKey); } // 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, 0, numbers.length-1, 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: 4 Search key index in Array of Integers: 3
Java Tutorial
Privacy Policy | Copyright2020 - All Rights Reserved. | Contact us
| Report website issues in Github
| Facebook page
| Google+ page