**Binary search**, also known as **half-interval search,binary chop or logarithmic search.**

## How it Works?

**Binary search** works on sorted arrays values. **Binary search** begins by comparing the middle element of the array with the target value. If the target value matches the middle element, its position in the array is returned. If the target value is less than or greater

than the middle element, the search continues in the lower or upper half of the array, respectively, eliminating the other half from consideration.If the search ends with the remaining half being empty, the target is not in the array.

**Time and Space Complexity?**

Binary search runs in at worst logarithmic time, making **O(log n)** comparisons and takes constant **(O(1))** space.

where **n** is the number of elements in the array, the **O** is **Big O** notation, and log is the logarithm.

## Java API for Binary Search

Java Arrays class also provide api’s for Binary Search. You can use as below

import java.util.Arrays; public class BinarySearchByJavaAPI { public static void main(String[] args) { char characters[] = { 'l', 'm', 'n', 'p', 'q<span data-mce-type="bookmark" id="mce_SELREST_start" data-mce-style="overflow:hidden;line-height:0" style="overflow:hidden;line-height:0" ></span>' }; System.out.println(Arrays.binarySearch(characters, 'a')); System.out.println(Arrays.binarySearch(characters, 'p')); } }

## Java Program for Binary Search

import java.util.Scanner; class BinarySearch { public static void main(String args[]) { int c, first, last, middle, n, search, array[]; Scanner in = new Scanner(System.in); System.out.println("Enter number of elements"); n = in.nextInt(); array = new int[n]; System.out.println("Enter " + n + " sorted integers"); for (c = 0; c < n; c++) array[c] = in.nextInt(); System.out.println("Enter value to find"); search = in.nextInt(); first = 0; last = n - 1; middle = (first + last)/2; while( first <= last ) { if ( array[middle] < search ) first = middle + 1; else if ( array[middle] == search ) { System.out.println(search + " found at location " + (middle + 1) + "."); break; } else last = middle - 1; middle = (first + last)/2; } if ( first ><span data-mce-type="bookmark" id="mce_SELREST_start" data-mce-style="overflow:hidden;line-height:0" style="overflow:hidden;line-height:0" ></span> last ) System.out.println(search + " is not present in the list.\n"); } }