BINARY SEARCH

In computer science, 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. If the search ends with the remaining half being empty, the target is not in the array.

Binary search runs in at worst logarithmic time, making O(log n) comparisons, where n is the number of elements in the array, the O is Big O notation, and log is the logarithm. Binary search takes constant (O(1)) space, meaning that the space taken by the algorithm is the same for any number of elements in the array. Although specialized data structures designed for fast searching—such as hash tables—can be searched more efficiently, binary search applies to a wider range of problems.

Although the idea is simple, implementing binary search correctly requires attention to some subtleties about its exit conditions and midpoint calculation.

There are numerous variations of binary search. In particular, fractional cascading speeds up binary searches for the same value in multiple arrays, efficiently solving a series of search problems in computational geometry and numerous other fields. Exponential search extends binary search to unbounded lists. The binary search tree and B-tree data structures are based on binary search.

Algorithm

Binary search works on sorted arrays. 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.

Procedure

Given an array A of n elements with values or records A₀, A₁, ..., A_n−1, sorted such that A₀ ≤ A₁ ≤ ... ≤ A_n−1, and target value T, the following subroutine uses binary search to find the index of T in A.

1. Set L to 0 and R to n − 1.
2. If L > R, the search terminates as unsuccessful.
3. Set m (the position of the middle element) to the floor (the largest previous integer) of (L + R) / 2.
4. If A_m < T, set L to m + 1 and go to step 2.
5. If A_m > T, set R to m − 1 and go to step 2.
6. Now A_m = T, the search is done; return m.

This iterative procedure keeps track of the search boundaries with two variables. Some implementations may check whether the middle element is equal to the target at the end of the procedure. This results in a faster comparison loop, but requires one more iteration on average.

Approximate matches

The above procedure only performs exact matches, finding the position of a target value. However, due to the ordered nature of sorted arrays, it is trivial to extend binary search to perform approximate matches. For example, binary search can be used to compute, for a given value, its rank (the number of smaller elements), predecessor (next-smallest element), successor (next-largest element), and nearest neighbor. Range queries seeking the number of elements between two values can be performed with two rank queries.

• Rank queries can be performed using a modified version of binary search. By returning m on a successful search, and L on an unsuccessful search, the number of elements less than the target value is returned instead.
• Predecessor and successor queries can be performed with rank queries. Once the rank of the target value is known, its predecessor is the element at the position given by its rank (as it is the largest element that is smaller than the target value). Its successor is the element after it (if it is present in the array) or at the next position after the predecessor (otherwise). The nearest neighbor of the target value is either its predecessor or successor, whichever is closer.
• Range queries are also straightforward. Once the ranks of the two values are known, the number of elements greater than or equal to the first value and less than the second is the difference of the two ranks. This count can be adjusted up or down by one according to whether the endpoints of the range should be considered to be part of the range and whether the array contains keys matching those endpoints.

Performance

A tree representing binary search. The array being searched here is [20, 30, 40, 50, 90, 100], and the target value is 40.

The performance of binary search can be analyzed by reducing the procedure to a binary comparison tree, where the root node is the middle element of the array; the middle element of the lower half is left of the root and the middle element of the upper half is right of the root. The rest of the tree is built in a similar fashion. This model represents binary search; starting from the root node, the left or right subtrees are traversed depending on whether the target value is less or more than the node under consideration, representing the successive elimination of elements.

The worst case is ${\textstyle \lfloor \log _{2}n+1\rfloor }$ iterations of the comparison loop, where the ${\textstyle \lfloor \rfloor }$ notation denotes the floor function that rounds its argument to the next-smallest integer and ${\textstyle \log _{2}}$ is the binary logarithm. The worst case is reached when the search reaches the deepest level of the tree, equivalent to a binary search that has reduced to one element and, in each iteration, always eliminates the smaller subarray out of the two if they are not of equal size.

On average, assuming that each element is equally likely to be searched, the procedure will most likely find the target value the second-deepest level of the tree. This is equivalent to a binary search that completes one iteration before the worst case, reached after ${\textstyle \log _{2}n-1}$ iterations. However, the tree may be unbalanced, with the deepest level partially filled, and equivalently, the array may not be divided perfectly by the search in some iterations, half of the time resulting in the smaller subarray being eliminated. The actual number of average iterations is slightly higher, at

 ${\textstyle \log _{2}n-{\frac {n-\log _{2}n-1}{n}}}$ iterations. In the best case, where target value is the middle element of the array, its position is returned after one iteration. In terms of iterations, no search algorithm that works only by comparing elements can exhibit better average and worst-case performance than binary search.^[12]

Each iteration of the binary search procedure defined above makes one or two comparisons, checking if the middle element is equal to the target in each iteration. Again assuming that each element is equally likely to be searched, each iteration makes 1.5 comparisons on average. A variation of the algorithm checks whether the middle element is equal to the target at the end of the search, eliminating on average half a comparison from each iteration. This slightly cuts the time taken per iteration on most computers, while guaranteeing that the search takes the maximum number of iterations, on average adding one iteration to the search. Because the comparison loop is performed only ${\textstyle \lfloor \log _{2}n+1\rfloor }$ times in the worst case, for all but enormous ${\textstyle n}$, the slight increase in comparison loop efficiency does not compensate for the extra iteration. Knuth 1998 gives a value of ${\textstyle 2^{66}}$ (more than 73 quintillion) elements for this variation to be faster.

Fractional cascading can be used to speed up searches of the same value in multiple arrays. Where ${\textstyle k}$ is the number of arrays, searching each array for the target value takes ${\textstyle O(k\log n)}$ time; fractional cascading reduces this to ${\textstyle O(k+\log n)}$.

Binary search versus other schemes

Sorted arrays with binary search are a very inefficient solution when insertion and deletion operations are interleaved with retrieval, taking ${\textstyle O(n)}$ time for each such operation, and complicating memory use. Other data structures support much more efficient insertion and deletion, and also fast exact matching. However, binary search applies to a wide range of search problems, usually solving them in ${\textstyle O(\log n)}$ time regardless of the type or structure of the values themselves.

Hashing

For implementing associative arrays, hash tables, a data structure that maps keys to records using a hash function, are generally faster than binary search on a sorted array of records; most implementations require only amortized constant time on average. However, hashing is not useful for approximate matches, such as computing the next-smallest, next-largest, and nearest key, as the only information given on a failed search is that the target is not present in any record. Binary search is ideal for such matches, performing them in logarithmic time. In addition, all operations possible on a sorted array can be performed—such as finding the smallest and largest key and performing range searches.

Trees

Binary search trees are searched using an algorithm similar to binary search.

A binary search tree is a binary tree data structure that works based on the principle of binary search. The records of the tree are arranged in sorted order, and each record in the tree can be searched using an algorithm similar to binary search, taking on average logarithmic time. Insertion and deletion also require on average logarithmic time in binary search trees. This can faster than the linear time insertion and deletion of sorted arrays, and binary trees retain the ability to perform all the operations possible on a sorted array, including range and approximate queries.

However, binary search is usually more efficient for searching as binary search trees will most likely be imperfectly balanced, resulting in slightly worse performance than binary search. This applies even to balanced binary search trees, binary search trees that balance their own nodes—as they rarely produce optimally-balanced trees—but to a lesser extent. Although unlikely, the tree may be severely imbalanced with few internal nodes with two children, resulting in the average and worst-case search time approaching ${\textstyle n}$ comparisons. Binary search trees take more space than sorted arrays.

Binary search trees lend themselves to fast searching in external memory stored in hard disks, as binary search trees can effectively be structured in filesystems. The B-tree generalizes this method of tree organization; B-trees are frequently used to organize long-term storage such as databases and filesystems.

Linear search

Linear search is a simple search algorithm that checks every record until it finds the target value. Linear search can be done on a linked list, which allows for faster insertion and deletion than an array. Binary search is faster than linear search for sorted arrays except if the array is short. If the array must first be sorted, that cost must be amortized over any searches. Sorting the array also enables efficient approximate matches and other operations.

Mixed approaches

The Judy array uses a combination of approaches to provide a highly efficient solution.

Set membership algorithms

A related problem to search is set membership. Any algorithm that does lookup, like binary search, can also be used for set membership. There are other algorithms that are more specifically suited for set membership. A bit array is the simplest, useful when the range of keys is limited; it is very fast, requiring only ${\textstyle O(1)}$ time. The Judy1 type of Judy array handles 64-bit keys efficiently.

For approximate results, Bloom filters, another probabilistic data structure based on hashing, store a set of keys by encoding the keys using a bit array and multiple hash functions. Bloom filters are much more space-efficient than bitarrays in most cases and not much slower: with ${\textstyle k}$ hash functions, membership queries require only ${\textstyle O(k)}$ time. However, Bloom filters suffer from false positives.

Java programming code

Binary Search Java Code And Explanation

1    int[] data;
2    int size;
3
4    public boolean binarySearch(int key) 
5    {
6         int low = 0;
7         int high = size - 1;
8          
9         while(high >= low) {
10             int middle = (low + high) / 2;
11             if(data[middle] == key) {
12                 return true;
13             }
14             if(data[middle] < key) {
15                 low = middle + 1;
16             }
17             if(data[middle] > key) {
18                 high = middle - 1;
19             }
20        }
21        return false;
22   }

Explanation:

• line 1: tells us that we have an array of integers called data. An array is just an ordered list of values, just like the list we talked about in our algorithm. An integer is a positive or negative whole number.
• line 2: size tells us the number of items that we have in the list.
• lines 4, 5, and 22: These lines tell us that the code between line 5 and 22 performs one task, and give the name binarySearch to the task. key is the target item that we will search for in data. The word boolean tells us that linearSearch will return true if it finds the key in the list, and it will return false if the key is not in the list.
• line 6: low is the variable that tells us where the beginning of the remaining list is, and we give it an initial value of 0.
• line 7: high is the variable that tells us where the end of the remaining list is, and we give it an initial value of the last thing in the list.
• line 9: This line tells us to keep going until low is bigger than or equal to high.
• line 10: middle we calculate so we can divide the list into two pieces.
• line 11, 12, 13: We found the key, so we return true.
• line 14, 15, 16: If the item in the middle of the list is less than our key, we should look for the key in the top half of the list, so we calculate a new value for low.
• line 17, 18, 19: If the item in the middle of the list is greater than our key, we should look for the key in the bottom half of the list, so we calculate a new value for high.
• line 21: If we get to this line then we know that the key is not in the list so we return false.

OTHER BINARY SEARCH CODE

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 + " 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 > last )
      System.out.println(search + " is not present in the list.\n");
  }
}

Output of program:

Other methods of searching are Linear search and Hashing. There is a binarySearch method in Arrays class which can also be used.

import java.util.Arrays;
 
class BS 
{
  public static void main(String args[])
  {
    char characters[] = { 'a', 'b', 'c', 'd', 'e' };
 
    System.out.println(Arrays.binarySearch(characters, 'a'));
    System.out.println(Arrays.binarySearch(characters, 'p'));
  }
}

binarySearch method returns the location if a match occurs otherwise -(x+1) where x is the no. of elements in the array, For example in the second case above when p is not present in characters array the returned value will be -6.

/* Java Program Example - Binary Search */
		
import java.util.Scanner;

public class JavaProgram
{
   public static void main(String args[])
   {
       int n, i, search, first, last, middle;
       int arr[] = new int[50];
       Scanner scan = new Scanner(System.in);
	   
       System.out.print("Enter Total Number of Elements : ");
       n = scan.nextInt();
	   
       System.out.print("Enter " +n+ " Elements : ");
       for(i=0; i<n; i++)
       {
           arr[i] = scan.nextInt();
       }
	   
       System.out.print("Enter a Number to Search..");
       search = scan.nextInt();
	   
       first = 0;
       last = n-1;
       middle = (first+last)/2;
	   
       while(first <= last)
       {
           if(arr[middle] < search)
           {
               first = middle+1;
           }
           else if(arr[middle] == search)
           {
               System.out.print(search+ " Found at Location " +middle);
               break;
           }
           else
           {
               last = middle - 1;
           }
           middle = (first+last)/2;
       }
       if(first > last)
       {
           System.out.print("Not Found..!! " +search+ " is not Present in the List.");
       }
   }
}

When the above Java Program is compile and executed, it will produce the following output. Above Java Programming Example Output (Element found):

Above Java Programming Example Output (Element Not found):

ANOTHER BINARY SEARCH PROGRAM

A binary search or half-interval search algorithm finds the position of a specified value (the input "key") within a sorted array. In each step, the algorithm compares the input key value with the key value of the middle element of the array. If the keys match, then a matching element has been found so its index, or position, is returned. Otherwise, if the sought 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 input key is greater, on the sub-array to the right. If the remaining array to be searched is reduced to zero, then the key cannot be found in the array and a special "Not found" indication is returned. Every iteration eliminates half of the remaining possibilities. This makes binary searches very efficient - even for large collections. Binary search requires a sorted collection. Also, binary searching can only be applied to a collection that allows random access (indexing). Worst case performance: O(log n) Best case performance: O(1) ? 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 package com.java2novice.algos; public class MyBinarySearch {     public int binarySearch(int[] inputArr, int key) {                   int start = 0;         int end = inputArr.length - 1;         while (start <= end) {             int mid = (start + end) / 2;             if (key == inputArr[mid]) {                 return mid;             }             if (key < inputArr[mid]) {                 end = mid - 1;             } else {                 start = mid + 1;             }         }         return -1;     }        public static void main(String[] args) {                   MyBinarySearch mbs = new MyBinarySearch();         int[] arr = {2, 4, 6, 8, 10, 12, 14, 16};         System.out.println("Key 14's position: "+mbs.binarySearch(arr, 14));         int[] arr1 = {6,34,78,123,432,900};         System.out.println("Key 432's position: "+mbs.binarySearch(arr1, 432));     } }

Output: Key 14's position: 6 Key 432's position: 4