Basic Overview Of Binary Search:
• A binary search algorithm finds the position of a specified input value within an array sorted by key value.
• For binary search, the array should be sorted i.e. arranged in ascending or descending order.
• In Binary search, the search key value with the key value of the middle element of the array. If the key element match, then a matching element has been found and its position, is returned.
• if the search key is less than the middle element's key, then the algorithm repeats its action on the sub-array to the left of the middle element or, if the search key is greater, on the sub-array to the right.
• If the remaining array to be searched is empty, then the key cannot be found in the array and a “key is not found” message returned.
Steps :
Create new java class as follows.
package com.search.binarySearch; import java.util.Scanner; public class BinarySearchImpl { public static void main(String args[]) { int counter, numberOfElements, key, array[], first, last, middle; //To get the user input Scanner input = new Scanner(System.in); System.out.println("Enter total number of elements :"); numberOfElements = input.nextInt(); //Creating array to store the numbers of size n array = new int[numberOfElements]; System.out.println("Enter " + numberOfElements + " integers"); //Loop to store each entered number in array for (counter = 0; counter < numberOfElements; counter++) array[counter] = input.nextInt(); System.out.println("Enter key value to find :"); key = input.nextInt(); first = 0; last = numberOfElements; middle = (first + last)/2; while( first <= last ) { if ( array[middle] < key ) first = middle + 1; else if ( array[middle] == key ) { System.out.println(key + " found at location " + (middle + 1) + "."); break; } else { last = middle - 1; } middle = (first + last)/2; } if ( first > last ) System.out.println(key + " is not found.\n"); } }