Binary search algorithm : Java code

A binary search or half-interval search algorithm finds the position of a target value within a sorted array.

Step#1 Find the mid_element of array and compare it to target_value.

Step#2 If target_value == mid_element,

                        return position

       If target_value < mid_element,

                        then the search continues on the lower half of the array;

       If target_value > mid_element,

                        then the search continues on the upper half of the array.

Step#3 Repeat the Step#2 (eliminating half of the elements) until the target value is either found, or until the entire array has been searched.

Complexity

Worst case performance O(log n)

Best case performance O(1)

Average case performance O(log n)

Worst case space complexity O(1)

Recursive approach

class Recursive {

    static int binary_search(int[] array,intkey,intimin,intimax){

        // test if array is empty

        if (imax < imin) {

            // set is empty, so return value showing not found

            return -1;

        } else {

            // calculate midpoint to cut set in half

            int imid = (imin+imax)/2;

            if (array[imid] > key) {

                // key is in lower subset

                return binary_search(array, key, imin, imid - 1);

            } else if(array[imid] < key) {

                // key is in upper subset

                return binary_search(array, key, imid + 1, imax);

            } else {

                // key has been found

                return imid;

            }

        }

    }

}

public class BinarySearch {

    public static void main(String[] args) {

        int[] array={1,4,5,7,8,9};

        int key=7;

        int idx=Recursive.binary_search(array,key,0,array.length-1);

        System.out.println("Using recursive approach.\n Index# "+idx);

    }

}

Output:

    Using recursive approach.

     Index# 3

Iterative approach

class Iterative {

    int binary_search(intarray[], intkey, intimin, intimax) {

        while (imin <= imax) {

            int imid = (imin+imax)/2;

            if (array[imid] == key) {

                // key found at index imid

                return imid;

            } else if(array[imid] < key) {

                // change min index to search upper subarray

                imin = imid + 1;

            } else {       

                // change max index to search lower subarray

                imax = imid - 1;

            }

        }

        // key was not found

        return -1;

    }

}

public class BinarySearch {

    public static void main(String[] args) {

        int[] array={1,4,5,7,8,9};

        int key=7;

                

        idx=Recursive.binary_search(array,key,0,array.length-1);

        System.out.println("Using iterative approach.\n Index# "+idx);

    }

}

Output:

    Using iterative approach.

     Index# 3

May be helpful:
Binary searching versus linear searching
Selection Sort: Java Code

References:

https://en.wikipedia.org/wiki/Binary_search_algorithm

Selection Sort: Java Code

Selection sort is noted for its simplicity, and it has advantages when auxiliary memory is limited.

The algorithm divides the input list into two parts:

1.The sublist of items already sorted, which is built up from left to right at the front (left) of the list, and

2. The sublist of items remaining to be sorted that occupy the rest of the list.

Initially, the sorted sublist is empty and the unsorted sublist is the entire input list. The algorithm proceeds by finding the smallest (or largest, depending on sorting order) element in the unsorted sublist, exchanging (swapping) it with the leftmost unsorted element (putting it in sorted order), and moving the sublist boundaries one element to the right.

Example:

54 35 22 32 21 // this is the initial, starting state of the array

21 35 22 32 54 // sorted sublist = {21}

21 2235 32 54 // sorted sublist = {21, 22}

21 22 32 35 54 // sorted sublist = {21, 22, 32}

21 22 32 35 54 // sorted sublist = {21, 22, 32, 35}

21 22 32 35 54 // sorted sublist = {21, 22, 32, 35, 54}

Complexity:

Best Case           :    O(n^2)

Average Case  :    O(n^2)

Worst Case      :    O(n^2)

importjava.util.Scanner;

public classSelectionSort {

     public static int[] sort(int[] arr) {

           // outer loop to maintain the index of sorted array.

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

                int index = i;

                // inner loop is searching in unsorted list.

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

                     // check for smallest number’s index.

                     if (arr[j] < arr[index]) {

                           index = j;

                     }

                }

                // swap with left most unsorted index.

                int smallerNumber = arr[index];

                arr[index] = arr[i];

                arr[i] = smallerNumber;

           }

           return arr;

     }

     public static void main(String...args) {

           Scanner scan = new Scanner(System.in);

           System.out.println("Enter the no. of elements:");

           int size = scan.nextInt();

           int[] array = new int[size];

          

           for(int i = 0;i<size;i++) {

                array[i] = scan.nextInt();

           }

           int[] sortedArray = sort(array);

           for(int e : sortedArray){

                System.out.print(e+" ");

           }

     }

}

Output:

Enter the no. of elements:

5

54 35 22 32 21

21 22 32 35 54 

References:

https://en.wikipedia.org/wiki/Selection_sort

Increment a number by one without using addition operator

Write a program to increment a number by one without using operators like ‘+’, ‘-‘, ‘*’, ‘/’, ‘++’, ‘–‘ …etc.

Examples:

Input: 20

Output: 21

We can achieve the functionality using bitwise operators.

Approach#

To increment the bit, we need to add 1 in binary representation. However addition is not allowed.

So we can check the each bit and flip it using bitwise operators.

Step#1 Flip all the set bits until we find a 0. (Alternate to Carry forward in addition)

Step#2 Flip the rightmost 0 bit (Add the new value at right side).

Bitwise representation of 20 is 10100.

public class IncrementByOne {

     public static void main(String[] args) {

           int value = 20;

           value = increment(20);

           System.out.println(value);

     }

     static intincrement(int number) {

           int one = 1;

           /* Flip all the set bits until we find a 0 */

           while((number & one)!=0 ) {

                number = number^one;

                one <<= 1;

           }

           /* flip the rightmost 0 bit */

           number = number^one;

           return number;

     }

}

Output:

21

Dependency Lookup

The Dependency Lookup is an approach where we get the resource after demand. Various ways to get the resource are mentioned below:

Using new keyword

ClassA obj = new ClassAImpl(); 

Static factory method

ClassA  obj = ClassA.getClassA(); 

Using JNDI (Java Naming Directory Interface) :

Context ctx = new InitialContext();

Context environmentCtx = (Context) ctx.lookup ("java:comp/env"); 

ClassA obj = (ClassA)environmentCtx.lookup("ClassA "); 

Problems of Dependency Lookup

Tight coupling: The dependency lookup approach makes the code tightly coupled. If resource is changed, we need to perform a lot of modification in the code.

Not easy for testing: This approach creates a lot of problems while testing the application especially in black box testing.

Dependency Injection (DI) is a design pattern that removes the dependency from the code so that it can be easy to manage and test the application. It makes our programming code loosely coupled.

This process is fundamentally the inverse, hence the name Inversion of Control (IoC), of the bean itself controlling the instantiation or location of its dependencies by using direct construction of classes, or a mechanism such as the Service Locator pattern.

The org.springframework.beans and org.springframework.context packages are the basis for Spring Framework’s IoC container.