Wednesday, February 1, 2023

Binary Search

Binary Search is a searching algorithm used in a sorted array by repeatedly dividing the search interval in half. The idea of binary search is to use the information that the array is sorted and reduce the time complexity to O(Log n). 

Binary Search Algorithm: The basic steps to perform Binary Search are:

  • Sort the array in ascending order.
  • Set the low index to the first element of the array and the high index to the last element.
  • Set the middle index to the average of the low and high indices.
  • If the element at the middle index is the target element, return the middle index.
  • If the target element is less than the element at the middle index, set the high index to the middle index – 1.
  • If the target element is greater than the element at the middle index, set the low index to the middle index + 1.
  • Repeat steps 3-6 until the element is found or it is clear that the element is not present in the array.

Binary Search Algorithm can be implemented in the following two ways

  1. Iterative Method
  2. Recursive Method

1. Iterative Method

binarySearch(arr, x, low, high)

        repeat till low = high

               mid = (low + high)/2

                   if (x == arr[mid])

                       return mid

                   else if (x > arr[mid]) // x is on the right side

                       low = mid + 1

                   else                  // x is on the left side

                       high = mid - 1


Iterative implementation of Binary Search 

// Java implementation of iterative Binary Search

class BinarySearch {

    // Returns index of x if it is present in arr[],

    // else return -1

    int binarySearch(int arr[], int x)

    {

        int l = 0, r = arr.length - 1;

        while (l <= r) {

            int m = l + (r - l) / 2;

            // Check if x is present at mid

            if (arr[m] == x)

                return m;

            // If x greater, ignore left half

            if (arr[m] < x)

                l = m + 1;

            // If x is smaller, ignore right half

            else

                r = m - 1;

        }

        // if we reach here, then element was

        // not present

        return -1;

    }

    // Driver method to test above

    public static void main(String args[])

    {

        BinarySearch ob = new BinarySearch();

        int arr[] = { 2, 3, 4, 10, 40 };

        int n = arr.length;

        int x = 10;

        int result = ob.binarySearch(arr, x);

        if (result == -1)

            System.out.println("Element not present");

        else

            System.out.println("Element found at "

                               + "index " + result);

    }

}

Output

Element is present at index 3

Time Complexity: O(log n)

Auxiliary Space: O(1)

   

2. Recursive Method (The recursive method follows the divide and conquer approach)

binarySearch(arr, x, low, high)

           if low > high

               return False 

           else

               mid = (low + high) / 2 

               if x == arr[mid]

                       return mid

               else if x > arr[mid]        // x is on the right side

                   return binarySearch(arr, x, mid + 1, high)

               else                        // x is on the left side

                   return binarySearch(arr, x, low, mid - 1) 


Recursive implementation of Binary Search:

// Java implementation of recursive Binary Search

class BinarySearch {

    // Returns index of x if it is present in arr[l..

    // r], else return -1

    int binarySearch(int arr[], int l, int r, int x)

    {

        if (r >= l) {

            int mid = l + (r - l) / 2;

             // If the element is present at the

            // middle itself

            if (arr[mid] == x)

                return mid;

             // If element is smaller than mid, then

            // it can only be present in left subarray

            if (arr[mid] > x)

                return binarySearch(arr, l, mid - 1, x);

             // Else the element can only be present

            // in right subarray

            return binarySearch(arr, mid + 1, r, x);

        }

         // We reach here when element is not present

        // in array

        return -1;

    }

     // Driver method to test above

    public static void main(String args[])

    {

        BinarySearch ob = new BinarySearch();

        int arr[] = { 2, 3, 4, 10, 40 };

        int n = arr.length;

        int x = 10;

        int result = ob.binarySearch(arr, 0, n - 1, x);

        if (result == -1)

            System.out.println("Element not present");

        else

            System.out.println("Element found at index "

                               + result);

    }

}


Output

Element is present at index 3

Time Complexity: O(log n)

Auxiliary Space: O(log n)

Advantages of Binary Search:

  • Binary search is faster than linear search, especially for large arrays. As the size of the array increases, the time it takes to perform a linear search increases linearly, while the time it takes to perform a binary search increases logarithmically.
  • Binary search is more efficient than other searching algorithms that have a similar time complexity, such as interpolation search or exponential search.
  • Binary search is relatively simple to implement and easy to understand, making it a good choice for many applications.
  • Binary search can be used on both sorted arrays and sorted linked lists, making it a flexible algorithm.
  • Binary search is well-suited for searching large datasets that are stored in external memory, such as on a hard drive or in the cloud.

Drawbacks of Binary Search:

  • We require the array to be sorted. If the array is not sorted, we must first sort it before performing the search. This adds an additional O(n log n) time complexity for the sorting step, which can make binary search less efficient for very small arrays.
  • Binary search requires that the array being searched be stored in contiguous memory locations. This can be a problem if the array is too large to fit in memory, or if the array is stored on external memory such as a hard drive or in the cloud.
  • Binary search requires that the elements of the array be comparable, meaning that they must be able to be ordered. This can be a problem if the elements of the array are not naturally ordered, or if the ordering is not well-defined.
  • Binary search can be less efficient than other algorithms, such as hash tables, for searching very large datasets that do not fit in memory.

Applications of Binary search:

  • Searching in machine learning: Binary search can be used as a building block for more complex algorithms used in machine learning, such as algorithms for training neural networks or finding the optimal hyperparameters for a model.
  • Commonly used in Competitive Programming.
  • Can be used for searching in computer graphics. Binary search can be used as a building block for more complex algorithms used in computer graphics, such as algorithms for ray tracing or texture mapping.
  • Can be used for searching a database. Binary search can be used to efficiently search a database of records, such as a customer database or a product catalog.

When to use Binary Search:

  • When searching a large dataset as it has a time complexity of O(log n), which means that it is much faster than linear search.
  • When the dataset is sorted.
  • When data is stored in contiguous memory.
  • Data does not have a complex structure or relationships.




Tuesday, January 31, 2023

Linear Search

 

Linear Search

Linear Search is defined as a sequential search algorithm that starts at one end and goes through each element of a list until the desired element is found, otherwise the search continues till the end of the data set. It is the easiest searching algorithm.

Linear Search Algorithm
Step 1: First, read the search element (Target element) in the array.
Step 2: In the second step compare the search element with the first element in the array.
Step 3: If both are matched, display “Target element is found” and terminate the Linear Search 
function.
Step 4: If both are not matched, compare the search element with the next element in the array.
Step 5: In this step, repeat steps 3 and 4 until the search (Target) element is compared with the 
last element of the array.
Step 6 – If the last element in the list does not match, the Linear Search Function will be 
terminated, and the message “Element is not found” will be displayed.

Follow the given steps to solve the problem:
  1. Set the first element of the array as the current element.
  2. If the current element is the target element, return its index.
  3. If the current element is not the target element and if there are more elements in the array, set the current element to the next element and repeat step 2.
  4. If the current element is not the target element and there are no more elements in the array, return -1 to indicate that the element was not found.
Example:
Given an array arr[] of N elements,
the task is to write a function to search a given element x in arr[].
Solution:
class LinearSearch { public static int search(int arr[], int x) { int N = arr.length; for (int i = 0; i < N; i++) { if (arr[i] == x) return i; } return -1; } // Driver's code public static void main(String args[]) { int arr[] = { 2, 3, 4, 10, 40 }; int x = 10; // Function call int result = search(arr, x); if (result == -1) System.out.print( "Element is not present in array"); else System.out.print("Element is present at index " + result); } } Output: Element is present at index 3 Time complexity: O(N) Auxiliary Space: O(1)

Linear search Recursive approach:


Follow the given steps to solve the problem:

  • If the size of the array is zero then, return -1, representing that the element is not found. This can also be treated as the base condition of a recursion call.
  • Otherwise, check if the element at the current index in the array is equal to the key or not i.e, arr[size – 1] == key
  • If equal, then return the index of the found key

Below is the implementation of the above approach:

// Java Recursive Code For Linear Search
import java.io.*;
 
class Test {
    static int arr[] = { 5, 15, 6, 9, 4 };
 
    // Recursive Method to search key in the array
    static int linearsearch(int arr[], int size, int key)
    {
        if (size == 0) {
            return -1;
        }
        else if (arr[size - 1] == key) {
            // Return the index of found key.
            return size - 1;
        }
        else {
            return linearsearch(arr, size - 1, key);
        }
    }
 
    // Driver method
    public static void main(String[] args)
    {
        int key = 4;
 
        // Function call to find key
        int index = linearsearch(arr, arr.length, key);
        if (index != -1)
            System.out.println(
                "The element " + key + " is found at "
                + index + " index of the given array.");
 
        else
            System.out.println("The element " + key
                               + " is not found.");
    }
}

Output
The element 4 is found at 4 index of the given array.

Time Complexity: O(N)
Auxiliary Space: O(N)

Advantages of Linear Search:
  • Linear search is simple to implement and easy to understand.
  • Linear search can be used irrespective of whether the array is sorted or not. It can be used on arrays of any data type.
  • Does not require any additional memory.
  • It is a well suited algorithm for small datasets.

Drawbacks of Linear Search:
  • Linear search has a time complexity of O(n), which in turn makes it slow for large datasets.
  • Not suitable for large array.
  • Linear search can be less efficient than other algorithms, such as hash tables.

When to use Linear Search:
  • When we are dealing with a small dataset.
  • When you need to find an exact value.
  • When you are searching a dataset stored in contiguous memory.
  • When you want to implement a simple algorithm.

Searching Algorithms

Searching algorithms are used to find a specific element in an array, string, linked list or some other data structure.

The most common searching algorithms are:

Linear Search : In this searching algorithm, we check the element iteratively from one end to the other.

Binary Search : In this type of the searching algorithm, we break the data structure into two equal parts and try to decide in which half we need to find for the elements.

Ternary Search : In this case, the array is divided into three parts and based on the values at partitioning positions we decide the segment where we need to find the required element.

Besides these, there are other searching algorithms like

  • Jump Search
  • Interpolation Search 
  • Exponential Search

Array

What is Array?


An array is a collection of items of the same variable type that are stored at contiguous memory locations. It is one of the most popular and simple data structures and often used to implement other data structures. Each item in array is indexed starting with 0.




Representation Of Array
The representation of an array can be defined by its declaration. A declaration means allocating memory for an array of a given size.

There are 2 types of Array:
  1. Static Array
  2. Dynamic Array

1. Static Array:
Static Arrays are arrays that are declared before runtime and are assigned values while writing the code. It allocates memory at compile-time whose size is fixed. We cannot alter the static array.
Example: int arr[] = { 1, 3, 4 }; // static integer array  

Advantages of Static Array

  • It has efficient execution time.
  • The lifetime of static allocation is the entire run time of the program.

Disadvantages of Static Array

  • In case more static data space is declared than needed, there is waste of space.
  • In case less static space is declared than needed, then it becomes impossible to expand this fixed size during run time.
Dynamic Array

If we want an array to be sized based on input from the user. In such a case, dynamic arrays allow us to specify the size of an array at run-time.
Example: int* arr = new int[3]; // dynamic integer array  

The dynamic array is a variable size list data structure. It grows automatically when we try to insert an element if there is no more space left for the new element. It allows us to add and remove elements. It allocates memory at run time using the heap. It can change its size during run time.


Monday, January 23, 2023

Learn Algorithms

 Below are the most commonly used Algorithms:

1. Searching Algorithm

2. Sorting Algorithm

3. Divide and Conquer Algorithm

4. Greedy Algorithm

5. Recursion

6. Backtracking Algorithm

7. Dynamic Programing

8. Pattern Searching

9. Mathematical Algorithm

10. Geometric Algorithm

11. Bitwise Algorithm

12. Randomized Algorithm

13. Batch and Bound Algorithm




Learn Data Structures

 Below are the most highly used Data Structures

1. Array

2. String

3. Linked List

4. Matrix/Grid

5. Stack

6. Queue

7. Heap

8. Hash

9. Tree Data Structure

10. Graph Data Structure

11. Trie Data Structure




Learn about Complexities


Learn about Complexities
The primary motive to use DSA is to solve a problem effectively and efficiently. How can you decide if a program written by you is efficient or not? This is measured by complexities. 

Complexity is of two types:
Time Complexity: Time complexity is used to measure the amount of time required to execute the code.
Space Complexity: Space complexity means the amount of space required to execute successfully the functionalities of the code. 

The time required for executing a code depends on several factors, such as: 

  • The number of operations performed in the program, 
  • The speed of the device, and also 
  • The speed of data transfer if being executed on an online platform. 

So how can we determine which one is efficient? The answer is the use of asymptotic notation. 

The following 3 asymptotic notations are mostly used to represent the time complexity of algorithms:

Big-O Notation (Ο) – Big-O notation specifically describes the worst-case scenario.
Omega Notation (Ω) – Omega(Ω) notation specifically describes the best-case scenario.
Theta Notation (θ) – This notation represents the average complexity of an algorithm.

The most used notation in the analysis of a code is the Big O Notation which gives an upper bound of the running time of the code (or the amount of memory used in terms of input size)

Below are the running Time complexity in terms of Big-O O(f(n))

O(n!) : Worst

O(nlogn) : Bad

O(n) : Fair

O(logn) : Good

O(1) : Best