Binary Search – different flavors

Binary search is one of the fundamental search algorithm in the field of computer science. It helps to find given element in a given sorted sequence.

I will be showing multiple flavours of binary search. In a given sorted sequence, it is quite possible that element is repeated as shown in Figure-01. In the given array ‘a’, as you can see, element 6 is present at 3 indices.

Figure-01: Sample sorted array

sample_array.png

I am going to show you 3 different flavours of binary iterative search algorithm

  1. Basic search (any index position of given element)
  2. First Occurrence (first occurrence of given element)
  3. Last Occurrence (last occurrence of given element)

Basic search approach

Below code snippet shows basic search approach to search for given key element in the sorted sequence with no particular preference to index position.As shown in Figure-01, element 6 is present in 3 index positions. When we run basic search approach, algorithm would return index position as 3 for given sample array.

public static int v1_basic(int[] a, int n, int key) {
        int index = -1;
        int low = 0;
        int high = n - 1;
        int mid = (low + high) / 2;
        while (low <= high) {
            if (key == a[mid]) {
                index = mid;
                break;
            } else if (key < a[mid]) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
            mid = (low + high) / 2;
        }
        return index;
    }

First Occurrence search approach

Below code snippet shows searching for first occurrence of given key element in the sorted sequence if key element is present in more than one index position.
As shown in Figure-01, element 6 is present in 3 index positions. When we run first occurrence search approach, algorithm should return index position as 2.

public static int v2_firstOccurence(int[] a, int n, int key) {
        int index = -1;
        int low = 0, high = n - 1, mid = (low + high) / 2;
        while (low <= high) {
            if (key == a[mid]) {
                index = mid;
                high = mid - 1;
            } else if (key < a[mid]) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
            mid = (low + high) / 2;
        }
        return index;
    }

Last Occurrence search approach

Below code snippet shows searching for last occurrence of given key element in the sorted sequence if key element is present in more than one index position.
As shown in Figure-01, element 6 is present in 3 index positions. When we run last occurrence search approach, algorithm should return index position as 4.

public static int v3_lastOccurence(int[] a, int n, int key) {
        int index = -1;
        int low = 0, high = n - 1, mid = (low + high) / 2;
        while (low <= high) {
            if (key == a[mid]) {
                index = mid;
                low = mid + 1;
            } else if (key < a[mid]) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
            mid = (low + high) / 2;
        }
        return index;
    }

Complete console based Java application

The complete console based java based application to choose algorithm, number of elements, key element is shown below.

package searching;

import java.text.MessageFormat;
import java.util.Scanner;

public class BinarySearch {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (true) {
            System.out.println("\n===New run===");
            System.out.println("Select algorithm(1:any_index 2:first_occurrence 3:last_occurrence):");
            int algoSelection = scanner.nextInt();
            String algoSelected = "any_index";
            System.out.println("Enter number of elements(0->Exit):");
            int n = scanner.nextInt();
            if (n == 0) {
                System.out.println("Program is existing. Bye!!!");
                break;
            }
            int[] a = new int[n];
            System.out.println(MessageFormat.format("Enter {0} elements:", n));
            for (int i = 0; i < n; i++) {
                a[i] = scanner.nextInt();
            }
            System.out.println("Enter key element:");
            int key = scanner.nextInt();
            int index = -1;
            if (algoSelection == 1) {
                index = v1_basic(a, n, key);
            } else if (algoSelection == 2) {
                algoSelected = "first_occurrence";
                index = v2_firstOccurence(a, n, key);
            } else if (algoSelection == 3) {
                algoSelected = "last_occurrence";
                index = v3_lastOccurence(a, n, key);
            } else {
                index = v1_basic(a, n, key);
            }

            System.out.println(MessageFormat.format("algo_selected={3} key={0} index={1} msg=key_{2}",
                    key,
                    index,
                    (index == -1 ? "not_found" : "found")
                    , algoSelected
            ));
        }
        scanner.close();
    }

    public static int v1_basic(int[] a, int n, int key) {
        int index = -1;
        int low = 0;
        int high = n - 1;
        int mid = (low + high) / 2;
        while (low <= high) {
            if (key == a[mid]) {
                index = mid;
                break;
            } else if (key < a[mid]) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
            mid = (low + high) / 2;
        }
        return index;
    }

    public static int v2_firstOccurence(int[] a, int n, int key) {
        int index = -1;
        int low = 0, high = n - 1, mid = (low + high) / 2;
        while (low <= high) {
            if (key == a[mid]) {
                index = mid;
                high = mid - 1;
            } else if (key < a[mid]) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
            mid = (low + high) / 2;
        }
        return index;
    }

    public static int v3_lastOccurence(int[] a, int n, int key) {
        int index = -1;
        int low = 0, high = n - 1, mid = (low + high) / 2;
        while (low <= high) {
            if (key == a[mid]) {
                index = mid;
                low = mid + 1;
            } else if (key < a[mid]) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
            mid = (low + high) / 2;
        }
        return index;
    }
}

Sample run

The sample output from sample application is shown below. The console based application keeps looping until 0 is entered to indicate that you would like to exit application.


===New run===
Select algorithm(1:any_index 2:first_occurrence 3:last_occurrence):
1
Enter number of elements(0->Exit):
7
Enter 7 elements:
4 5 6 6 6 7 8
Enter key element:
6
algo_selected=any_index key=6 index=3 msg=key_found

===New run===
Select algorithm(1:any_index 2:first_occurrence 3:last_occurrence):

2
Enter number of elements(0->Exit):
7
Enter 7 elements:
4 5 6 6 6 7 8
Enter key element:
6
algo_selected=first_occurrence key=6 index=2 msg=key_found

===New run===
Select algorithm(1:any_index 2:first_occurrence 3:last_occurrence):
3
Enter number of elements(0->Exit):
7
Enter 7 elements:
4 5 6 6 6 7 8
Enter key element:
6
algo_selected=last_occurrence key=6 index=4 msg=key_found

===New run===
Select algorithm(1:any_index 2:first_occurrence 3:last_occurrence):
1
Enter number of elements(0->Exit):
0
Program is existing. Bye!!!

Process finished with exit code 0

Advertisements

One thought on “Binary Search – different flavors

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s