Binary Search Algorithm

Binary search also known as half-interval search, finds the index of a given integer (key) from a sorted array. 

 If the given integer is found, it returns the index of the integer inside array (positive value between 0 and n-1)

 Else it returns -1 (negative number that suggests that value don't exist in the array).

For example, suppose the given sorted array is:

                     

                                                                   Figure:  1

Simulation:
Input    : The integer that needs to be searched in the index
Output : Index of the integer found in array. (-1 means value not found)

Example 1:
Input:  5.
Output: 2.

Example 2:
Input:  1.
Output: 0.

Example 3:
Input:  25.
Output: -1.

Basic:  

In order to apply binary search on a given array of integers, the given array should be sorted (either in ascending or descending order).  Suppose the given sorted array  is arr[] whose length is n. We will be using the following terms during the explanation of binary search:

arr     -  given sorted array.
n       -  size of the array.
key  -   the number that needs to be searched in the array.
start   - index of first element of array.
end    - index of the last element of array + 1.
mid    - denotes the middle index of the array that we are sending in the algorithm.

Algorithm:

 binarySearch(arr, start, end, key)  {

     if (start < end) {

         mid = (start + end) / 2;   // get middle index of array.

         if(arr[mid] == key)   // check if middle element matches key

             return mid;      

         else if (arr[mid] < key)  // check if value exists in left sub array

   return binarySearch(arr, start, mid, key);  // perform binarySearch on left sub array

else
return binarySearch(arr, mid + 1, end, key);  // perform binarySearch on right sub array
     }

     return -1;  // value not found.

}

Explanation:

(Note: For current explanation, we consider that the array is sorted in ascending order)

The binarySearch function takes the following parameters as input:

arr - given array

start - start of array

end - size of array.

key - value to be found.

The above pseudocode is recursive approach to binary search.  For each iteration it performs the following steps: 

For our example, the values we are going to use are:

arr = {1, 3, 5, 10, 19, 23}

start = 0

end = 5

key = 23

Initially we check whether start < end.  This is done to make sure that our current index is within the range of the array.   

1) Find the middle element: 

In binary search, the first step is to find the middle index of the array.  We do this by taking average of start and end index of the array.

         mid = (start + end) / 2;

                                                                    Figure:  2

 In current example, start = 0, end  = 5.

mid = (start + end) / 2

      = (0 + 5) / 2

      = 3 

2) Check the middle element: 

Now, we have divided array into 3 parts:

          1) Middle element

          2) Left Sub array (Elements of array on left of the middle element)

          3) Right Sub array (Elements of array on right of the middle element)

First we check whether the middle element of array matches key or not.  If it matches return the index of the middle element.

         if(arr[mid] == key)

             return mid;

Here mid = 3, if the key we were searching for was 10, then arr[mid] would be equal to key and it would return the mid = 3.  But in our example key = 23, so it will bypass this condition.

3) Check Left Sub array: 

If the middle element does not match with given value, we check whether the element exists in the left sub array or not. To do this we simply check whether the middle element value is greater than key or not. If middle element is greater than key, then it follows that all elements on right sub array are greater than key (as the array is sorted in ascending order). So in this step we perform recursive call to perform binary search on left sub array. To do this we send start as starting index and mid as ending index. 

         else if (arr[mid] < key)

   return binarySearch(arr, start, mid, key);

 If key was less than arr[mid],  then key exists in the left sub array. As shown in figure 2, for left sub array:

start = 0

end  = ( index of last element of left sub array +  1 )

        = 2 + 1 

        = 3 (which is same as mid).

Thus while calling binary search recursively, we send start and mid to denote left sub array.

4) Check Right Sub array:

In above steps we already checked whether that key does not match middle element and it does not exist in the left sub array.  So the only possibility of existence of key on array is on the right sub array. So in this step we perform recursive call to perform binary search on right sub array.

else
return binarySearch(arr, mid + 1, end, key);

From above steps we can say that key may possibly exist in the right sub array. As shown in figure 2, for right sub array:

start = starting index of the right sub array (index of element after mid)

        = mid + 1

        = 4

end   =  5.

Thus while calling binary search recursively, we send (mid+1) and end to denote right sub array.

We perform this recursively until the key is found, or till the condition start < end fails.  If the condition fails, it means we have searched the whole array and the value is not found. So we return -1 to denote that value was not found in array.

Run time:  

If we divide the array recursively from mid and form a tree where root is middle element, left sub-tree is formed from left sub array and right sub-tree is formed from right sub array, we get a tree as shown below from the given array.

  

If we look closely to the newly obtained tree from the array, we can see that the tree is actually a binary search tree.  Now when we perform binary search on an array, we simply perform search on the binary search tree from root to leaves.  

The height of the tree = log(size of the array) = log(n). 

For our example size of array is 6.

Height of tree = log(6) = 3.

Thus, every time we perform binary search on an array, the run time will never exceed the height of tree, which is log(n). 

Thus the worst case run time of binary search is O( log(n) ).

If the key is same as middle element of the array, then we obtain the result in 1 step.  Thus the best case run-time of binary search is O(1)

The average case run-time of binary search is O( log(n) ).

Recursive Binary Search Implementation in Java:

public class BinarySearch {

private int[] arr;
int key;

void setValues(int[] arr, int key) {
this.arr = arr;
this.key = key;
}

int binarySearch(int start, int end) {

if (start < end) {

int mid = (start + end) / 2;

   // checks if value is found or not.
if (arr[mid] == key)
return mid;  // returns index if value is found.
else if (arr[mid] > key)
return binarySearch(start, mid);
else
return binarySearch(mid + 1, end);

}

return -1;  // value not found
}

public static void main(String[] args) {

int[] arr = { 1, 2, 3, 5, 6, 7, 9, 10 };
BinarySearch obj = new BinarySearch();
obj.setValues(arr, 2);
int keyIndex = obj.binarySearch(0, arr.length);

if (keyIndex != -1)
System.out.println("Value found at Index : "+keyIndex);
else
System.out.println("Value not found");
}
}

Find Duplicate Elements in Array

Given an array. Find duplicate elements in that array.

Solution:

(Note: we assume that the range is not provided and the array can contain both negative and positive numbers. The length of the given array is n. To find duplicates in array with given range visit here).

The solution can be achieved with two ways:

1) By improving the run time but sacrificing the space time.

2) By improving the space time by sacrificing the run time.

Solution 1: Run time : O(n), space time: O(n).

This can be achieved by using a hash map.  The following steps are involved for achieving the solution

i)   Iterate through array and store all elements in a hash map with key = element, value = no of occurrence.

     we store the occurrence in value to avoid printing the same duplicate element again as we iterate through     

     the array. We will increment the counter of value for each occurrence of the element. So that if the value 

     of the element is more than 1, means we already encountered the duplicate elements and it is printed in 

     previous iterations.(e.g. if array contains duplicate value 10 times, program will print duplicate value only 

     once).

ii)  If the element is already present in the hash map (i.e. that element is already encountered while reading array) and the occurrence of that element is 0 (means we encountered the duplicate element for first time),  print that element (duplicate element). 

Java Implementation: 

import java.util.HashMap;

/*

 * Program to find duplicate elements in an array.

 */

public class FindDuplicatesInArray {

/*

* Method to find duplicates in array.

* 

* @param: Array for which the duplicates are to be found.

*/

public void findDuplicate(int[] arr) {

HashMap map = new HashMap();

for (int i = 0; i < arr.length; i++) {

// first we check whether elements already exists in map or not

if (map.containsKey(arr[i])) {

// we do 2nd check to avoid printing the duplicate elements

// again every time we encounter the same element in array as we

// move forward.

if (map.get(arr[i]) == 0) {

System.out.println("Duplicate Element Found : " + arr[i]);

} else {

                                        // we increment value to keep track of number of occurrence

                                       // of that element.

int value = map.get(arr[i]);

value++;

map.put(arr[i], value);

}

} else {

// if element not present in hash map, put value in hash map

// with value 0.

map.put(arr[i], 0);

}

}

}

public static void main(String args[]) {

int arr[] = { 1, 2, 3, 4, 2, 1, 4, 5, 6, 7 };

new FindDuplicatesInArray().findDuplicate(arr);

}

}

During the program we are iterating through the array of size n. So the run time will be O(n). We also created a hash map to store the elements of array while iterating through it. Now in worst case all the elements of array are distinct, for which we will have to store the whole array in the hash map.  This will require O(n) space time.  

Solution 2: Run time : O(nlogn), space time: O(1).

This can be achieved by simply applying simple sorting and searching on given array. The following steps are involved for achieving the solution

i)  Sort the given array by using a in place merge sort.

ii) Iterate through the array, if the next element of the array is same as current element, print the element as duplicate.

iii) skip all occurrence of the duplicate elements and continue step(ii).

The sorting of array is required to align all the duplicate elements together.  We use merge sort as the best, average and worst run time of merge sort is nlogn.  (For more info on merge sort and its implementation visit here).

While we iterate through the array, we check whether the next element is same as current element as in sorted array the duplicates will be in row.  (Note: if the current element is last element of array, we don't need to check for next element).

Java Implementation:

import java.util.Arrays;

/*

 * Program to find duplicate elements in an array.

 */

public class FindDuplicatesInArray {

/*

* Method to find duplicates in array.

* 

* @param: Array for which the duplicates are to be found.

*/

public void findDuplicate(int[] arr) {

// By default java java collections have in-place merge sort

// as their generic sorting algorithm.

Arrays.sort(arr);

// we iterate through only 0 to (n - 1) to skip last element

// of array.

for (int i = 0; i < arr.length - 1; i++) {

if (arr[i] == arr[i + 1]) {

System.out.println("Duplicate element found: " + arr[i]);

// we skip all duplicate elements.

while (true) {

if (arr[i] == arr[i + 1] && i < arr.length - 1) {

i++;

}

else {

break;

}

}

}

}

}

public static void main(String args[]) {

int arr[] = { 1, 2, 3, 4, 2, 1, 4, 5, 6, 7 };

new FindDuplicatesInArray().findDuplicate(arr);

}

}

During the program, we are performing merge sort on the given array (For more info on merge sort and its implementation visit here).  The run time for merge sort is O(nlogn).  Also when we iterate through the array, we don't need extra space and run time for that is O(n). So total run time is :  nlogn + n = nlogn. As we don't consume extra space the space time is constant. (i.e. O(1)).

Find Duplicate Elements in an Array with elements in given range

Given an array of size n. It contains numbers in the range 1 to n. Each number is present at least once except for 2 numbers. Find the missing numbers.

Solution:

(Note: Here we make assumption that all the elements in array are positive.  For solution of finding duplicate in array where range is not given, visit here).

The main idea of the solution is to make use of the fact that the given numbers are in given range n and the size of the array is also n.  Basically we can map each element's value with the index of the array to create a key-value relation.

//Start iterating from first element of the array.
for(int i=0 to n)                                          
         //Get value of element at that index (say val).
         //Check if array[val] is > 0 or not.
         if(array[ abs(array[i]) - 1] > 0)
                 //If it is greater than 0, multiply it with -1. In the beginning all the elements are array are
                 // positive. Multiplying it with -1 makes it negative and makes sure that the particular element is
                 //visited.
                 array [ abs(array[i]) - 1 ] =  array [ abs(array[i]) - 1 ] * -1;

         //Else do nothing.

// If a particular number occurs only once, its value at end of iteration should be negative.  If it occurs two times, the number number will be positive and that indicates that its duplicate.
Iterate through the array again. Find all the elements who's value if greater than 0.  Print those elements as  duplicates.

Java Implementation:

public class FindDuplicateInArrayWithGivenRange {

public void findDuplicates(int[] arr) {

for (int i = 0; i < arr.length; i++) {
if (arr[Math.abs(arr[i]) - 1] > 0)
arr[Math.abs(arr[i]) - 1] = arr[Math.abs(arr[i]) - 1] * -1;
}

for (int i = 0; i < arr.length; i++)
if (arr[i] > 0) {
System.out.print(arr[i] + " ");
}
}

public static void main(String args[]) {

int[] arr = { 1, 3, 4, 2, 5, 2, 3 };
new FindDuplicateInArrayWithGivenRange().findDuplicates(arr);
}
}


We iterate through the array two times so the run time is n + n = 2n = O(n).
As we don't need any extra space for our calculation, the space time is constant = O(1).

Next Highest Number in Sequence

  Find the next highest number in the given sequence.  
  example:
  input : 54821
  output: 58412

 
   Solution: 

/*
 *
 *  1) Search for a non increasing number from right to left in the given sequence, suppose that number is x.
 *  2) Now find largest number < x from right, suppose that number is y.
 *  3) swap x and y.
 *
 *  Runtime: O(n).
 */
public class NextHighestNumberFromGivenSequence {

public int getNextHighestNumber(int[] currSeq) {

int nextNum = 0;
int x = -1;

for (int i = currSeq.length - 1; i > 0; i--) {
if (currSeq[i] > currSeq[i - 1]) {
x = i - 1;
break;
}
}

if (x != -1) {
for (int i = currSeq.length - 1; i > 0; i--) {
if (currSeq[i] > currSeq[x]) {
int temp = currSeq[x];
currSeq[x] = currSeq[i];
currSeq[i] = temp;
break;
}
}
}

for (int i = 0; i < currSeq.length; i++) {

if (i != 0)
nextNum = nextNum * 10;
nextNum = nextNum + currSeq[i];
}

return nextNum;
}


public static void main(String args[]) {

int[] arr = { 1, 2, 3, 4 };
System.out.println(new NextHighestNumberFromGivenSequence()
.getNextHighestNumber(arr));
}
}

Find Minimum SubArray

import java.util.LinkedList;
import java.util.Queue;

/*
 * Question:
   
   Given an array containing only 0s and 1s, find the minimum size of sub array containing exactly k-zeros.
    Ex. 11010100011   k=4
    result = 5(01000)

 * Solution:
 *
 * Runtime: O(n)
 * Space time: O(n)
 */

public class MinSubArrayQuestion1 {

public void findMinSubArr(int[] arr, int k) {

Queue queue = new LinkedList();
int minSubArrSize = arr.length;

for (int i = 0; i < arr.length; i++) {

if(arr[i] == 0) {

if(queue.size() != k){
queue.add(i);
}
else {
if(minSubArrSize > i - queue.peek() + 1) {
minSubArrSize = i - queue.peek() + 1;
}
queue.remove();
queue.add(i);
}
}
}


// Printing result.
if(queue.size() == k) {
System.out.print("Min SubArray : ");

for(int i = queue.peek(); queue.size() != 0; i++) {

if(i == queue.peek())
queue.remove();

System.out.print(arr[i]);
}
}
else {
System.out.println("No subarray found");
}
}


public static void main(String args[]) {

int[] arr = { 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1 };
new MinSubArrayQuestion1().findMinSubArr(arr, 5);
}

}

Merge Two Sorted Arrays

/*
 * Question:
   Given two sorted arrays A1 and A2, of lengths L1 and L2 , L1 < L2 and the last L1
   slots in A2 are vacant, get me all the numbers in A2, sorted in the most efficient
   manner without using extra space.
 
 * Solution:  
 * (Same question can be asked for merging more than 2 arrays
 *  follow the same pattern by merging 1 array with main array at a time)
 *
 *  Run a for loop from end of A2 and compare A1 and A2 from their ends.
 *
 *  Runtime: O(n);
 *  Space time: O(1);
 */
public class MergeTwoSortedArrays {

private int[] A1;
private int[] A2;

public MergeTwoSortedArrays() {
A1 = new int[4];
A2 = new int[10];

A1[0]= 2;
A1[1]= 4;
A1[2]= 7;
A1[3]= 9;

A2[0]= 1;
A2[1]= 3;
A2[2]= 5;
A2[3]= 6;
A2[4]= 8;
A2[5]= 10;
}

public void mergeTwoArrays(){

int l2 = 5;
int l1 = 3;
for(int i = A2.length-1; i>=0; i--) {

if(l1 >=0) {
if(A2[l2] > A1[l1]) {
A2[i] = A2[l2];
l2--;
}
else {
A2[i] = A1[l1];
l1--;
}
}
else {
break;
}
}
}

public void display() {

for(int i=0; i System.out.print(A2[i]+" ");
}
}

public static void main(String args[]) {

MergeTwoSortedArrays obj = new MergeTwoSortedArrays();

obj.mergeTwoArrays();
obj.display();
}
}

Count Swaps to Sort

/*
 * Question:
   Given an array containing sequence of bits (0 or 1), you have to sort this array
   in the ascending order i.e. all 0' in first part of array followed by all 1's.
   The constraints is that you can swap only the adjacent elements in the array.
   Find the minimum number of swaps required to sort the given input array.
 
 * Example: Given the array (0,0,1,0,1,0,1,1) the minimum number of swaps is 3.
 *
 * Note: You just need to complete the function given below for this task. The function is given a binary
    string as input and returns the required answer.
 *
 * Solution: 
 * Iterate from beginning of array. keep a counter of no of 1's in path.
 *
 * int swaps = 0;
 *
 * 1) For each '1' encountered increment counter by 1
 * 2) if '0' is encountered,  swaps = swaps + counter
 *
 * Finally print swaps.
 *
 * Runtime: O(n).
 * Spacetime: O(1).
 */

public class CountSwapsToSort {

int getNoOfSwaps(int[] arr) {

int swaps = 0;
int count = 0;

for (int i = 0; i < arr.length; i++) {
if (arr[i] == 1)
count++;
else
swaps = swaps + count;
}

return swaps;
}

public static void main(String args[]) {

int[] arr = { 1, 1, 1, 0, 0, 0 };
System.out.println(new CountSwapsToSort().getNoOfSwaps(arr));
}
}