Binary searching versus linear searching

Linear search

In linear search, we start searching of value from start until the value is not found or end of file. If it is, then you can stop searching and report that you have found the record.

Input A[n + 1] and x.

Set i to 1.

Repeat this loop:

     If A[i] = x, then exit the loop.

     Set i to i + 1.

Return i.

Complexity: O(n).

Pros:

Serial searching is excellent if your records are unordered.

Compared to a binary search, serial searching is a very easy to implement.

Cons:

Serial searching isn’t very efficient. That's because it takes lots of comparisons to find a particular record in big files, compared to binary searching. It takes longer on average to find a record in a big file compared to binary searching.

Example: For a file of size 2^20, there are 2^20 comparisons required in worst case.

Binary search

BinarySearch(A[0..N-1], value) {

      low = 0

      high = N - 1

      while (low <= high) {

          mid = (low + high)/2

          if (A[mid] > value)

              high = mid - 1

          else if (A[mid] < value)

              low = mid + 1

          else

              return mid

      }

      return not_found

}

Complexity: O(logn).

Pros:

Compared to a linear search, binary searching is a very efficient.

Example: For a file of size 2^20, there are 20 comparisons required in worst case.

Comparisons required: log(2^20) = 20.

Cons:

Binary searching cannot be applied on the unordered array.

It is little complex to write binary search compare to linear search.

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