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

[Hystrix Series] [Part1] Getting started with Hystrix

What is Hystrix?

Hystrix is a latency and fault tolerance java library designed to isolate points of access to remote systems, services and 3rd party libraries in a distributed environment. It helps to stop cascading failure and enable resilience in complex distributed systems where failure is inevitable.

How to add hystrix as library to your java application?

Hystrix can be added as maven library dependency to your Java application by adding below dependency declaration into your pom.xml.

Code Listing 1.1 : Showing Hystrix library ‘s maven dependency declaration

<dependency>
 <groupId>com.netflix.hystrix</groupId>
 <artifactId>hystrix-core</artifactId>
 <version>1.3.18</version>
</dependency>

The above declaration should pull all its transitive dependencies and makes the programmer life easier. To know more about, how to work with maven enabled Java project, please go through the link,  Apache Maven in 5 minutes.

Code your first Java generics based hystrix command

Creating your first Hystrix command involves creating a subclass of HystrixCommand API.

Let’s take an example to start with. We know that in an distributed enterprise application, it is quite common to see service oriented architecture where one service calls another service. Enterprise portal service is a SSO login which integrates multiple remote services. Here, enterprise portal service calls one such service called employee information service to fetch employee related information from employee directory based on search terms.

For portal service, employee information service is a point of access to remote system which only means a point of possible failure resulting in cascading failure for portal service as well. To prevent such a scenario where portal service continues to stay resilient despite employee information service being down is something we can achieve via hystrix.

The interaction between portal service and employee information service is depicted in the below diagram.

Diagram 1.1: Showing interaction between Portal Service and Employee Service

hsytrix

Let us assume that URL to access employee service is as shown below,

http://<host>:<port>/app/employees?terms="alex"

Currently I have hosted employee information service as RESTful webservice API. I have used Jersey client library to access RESTful web service. Client code to access employee information service is as shown below without using Hystrix.

Code Listing 1.2: Showing Client side code snippet on fetching employee information for given search terms

Client client = Client.create();
WebResource webResource = client.resource("http://localhost:9999/app/employees");
webResource.queryParam("terms", params);
String employeesList = webResource.get(String.class);

Now, we know that Portal Service is bound to resiliency issues.If employee information service goes down or service not responding or call times out, then these failures get cascaded to portal service as well which is not desirable. It would be better for portal service to build resiliency around all outbound calls such as employee information service,so that it can continue to serve the portal users need despite failures in some of the dependent remote services such as this one.

How to make portal service resilient to failures on remote service side?

The component which calls remote employee information service should be made resilient by wrapping it in Hystrix Command class so that you can define behavior on what should happen when remote service crosses Service Level Agreement(SLA) on response time. Let us say there is an SLA for employee information service to respond with necessary data within 2 seconds. If remote employee information service fails to responds to respond within 2 seconds, then what portal service should do? Should portal service timeout request to employee service or do something else like sending responses from cache  Response caching is one way to solve it. Another way, would be asking portal service to comeback after sometime. As long as portal is responsive by wrapping outbound network calls like remote employee service call, users are not frustrated.

The below code listing 1.3 shows how to wrap client code snippet in an hystrix command. This should be plain simple as long as you got the basics of how to use Hystrix library in right way.

Code Listing 1.3: Client code wrapped in HystrixCommand class to introduce resiliency around outbound network call.

public class EmployeeInformationCommand extends HystrixCommand {

    public EmployeeInformationCommand() {
        super(HystrixCommandGroupKey.Factory.asKey("EmployeeServiceGroup"));
    }

    @Override
    protected String run() throws Exception {
        Client client = Client.create();
        WebResource webResource = client.resource("http://localhost:9999/app/employees");
        webResource.queryParam("terms", params);
        String employeesList = webResource.get(String.class);
        return employeesList;
    }
}

As shown in the above code snippet, create a class which extends HystrixCommand where T stands for generic return type. In our case, we return String type object from run() method. One has to move client side code inside run method as shown. It is same exact code just executed inside another class which provides much more capabilities when we do it.

If you have already observed EmployeeInformationCommand’s default constructor, there is one important thing which I am doing which is essential to running as Hystrix Command. Gather all employee related commands under one group, ‘EmployeeServiceGroup’. It is mandatory to provide such logic group name to run code via hystrix library.

How to run Hystrix command?

Please keep in mind that, calling hystrix command execution is a blocking call. There are many other ways to run it as well. This is just for starters.

Code Listing 1.4: Calling hystrix command

new EmployeeInformationCommand().execute();

As shown above, it is that simple. When portal service wants to call hystrix wrapped outbound call, it is just one line of code.

Peek into Hystrix’s runtime configuration per command

Configuring hystrix command is quite simple, just that you have to follow convention on how you pass configuration key name per command.

For example, by default, hystrix command times out command execution if it doesn’t complete its execution within 1 second(1000 milli seconds).

The default property name across all commands is

Code Listing 1.5: default timeout property key 

hystrix.command.default.execution.isolation.thread.timeoutInMilliseconds

Also, per command level property to configure timeout has pattern,

Code Listing 1.6: Command instance level property key pattern

hystrix.command.<HystrixCommandKey>.execution.isolation.thread.timeoutInMilliseconds

When you want to override this particular property for our EmployeeInformationCommand class,  replace “HystrixCommandKey” with group name ” EmployeeInformationCommand”. You are done. Go ahead and mention that inside default constructor as shown below,

Code Listing 1.7: Actual property override declaration

public EmployeeInformationCommand() {
    super(HystrixCommandGroupKey.Factory.asKey("EmployeeServiceGroup"));

    ConfigurationManager.getConfigInstance().setProperty(
"hystrix.command.EmployeeInformationCommand.execution.isolation.thread.timeoutInMilliseconds",new Long(2000));
}

The above code listing informs hystrix to timeout if response is NOT received within 2 seconds(2000 milliseconds).

Please find the below code listing for complete hystrix command class.

Code Listing 1.8: Complete hystrix command source code

public class EmployeeInformationCommand extends HystrixCommand {

    private String params;

    public void setParams(String params) {
        this.params = params;
    }

    public EmployeeInformationCommand() {
        super(HystrixCommandGroupKey.Factory.asKey("EmployeeServiceGroup"));

        ConfigurationManager.getConfigInstance().setProperty(
                "hystrix.command.EmployeeServiceGroup.execution.isolation.thread.timeoutInMilliseconds",
                new Long(2000));
    }

    @Override
    protected String run() throws Exception {
        Client client = Client.create();
        WebResource webResource = client.resource("http://localhost:9999/app/employees");
        webResource.queryParam("terms", params);
        return webResource.get(String.class);
    }
}

When we are overriding configuration properties, it is always best to externalize them to properties file, so that we can modify them for running application to pick new configuration without recompiling source code again and again. An application restart will do the job.