###### Binary Search Algorithm

Binary search algorithm requires already sorted collection.

Binary search, (also known as half-interval search, logarithmic search, or binary chop) is a search algorithm that finds the position of a target value within a sorted array.

Binary search compares the target value to the middle element of the array. If they are unequal, the half in which the target cannot lie is eliminated and the search continues on the remaining half until it is successful or the remaining half is empty.

Once the target element found or collection is empty, then the search is over.

###### Performance

- Worst-case performance:- O(log n)
- Best-case performance:- O(1)
- Average performance:- O(log n)
- Worst-case space complexity:- O(1)

###### Java Program Of Binary Search

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
package com.codenuclear; public class BinarySearch { public static int binarySearch(int[] inputArray,int key) { int start = 0; int end = inputArray.length - 1; while (start <= end) { int mid = (start + end) / 2; if (key == inputArray[mid]) { return mid; } if (key < inputArray[mid]) { end = mid - 1; } else { start = mid + 1; } } return -1; } public static void main(String args[]) { int[] arr1 = {1,5,20,35,50,65,70}; int key = 100; int result = binarySearch(arr1,key); System.out.println( (result != -1) ? "Required key:- "+key+" found at index:- "+result : "Key "+key+ " not found"); //try with another key key = 50; result = binarySearch(arr1,key); System.out.println( (result != -1) ? "Required key:- "+key+" found at index:- "+result : "Key "+key+ " not found"); } } |

Output

Some theory part of this article uses material from the Wikipedia article “Binary search”, which is released under the CC BY-SA 3.0.