Binary Search

Binary search is a popular search algorithm that works on sorted arrays or lists. It's an efficient way to find a specific target element within a collection of data. Here's a detailed algorithm for binary search, along with a real-time example.

Binary Search Algorithm:

Binary search works by repeatedly dividing the search interval in half. It compares the middle element of the current interval with the target element. If the middle element matches the target, the search is successful. If not, it narrows down the search interval to the left or right half, depending on whether the target is greater or less than the middle element. This process continues until the target element is found or the search interval becomes empty.

Input:
arr: A sorted array (or list) of elements.
target: The element you want to find in the array.
Initialization:
Initialize two pointers, left and right, to the first and last indices of the array, respectively.
Search Loop:
While left is less than or equal to right, repeat the following steps:
    Calculate the middle index as mid using the formula: mid = (left + right) / 2.
    Compare the element at index mid with the target element:
        If arr[mid] is equal to target, you have               found the element, so return mid as the index of the
         target element.
       If arr[mid] is less than target, update left to mid + 1 to search in the right half of the current interval.
       If arr[mid] is greater than target, update right to mid - 1 to search in the left half of the current  
       interval.

Target Not Found:If the loop terminates (i.e., left becomes greater than right) and the target element has not been found, return -1 to indicate that the element is not in the array.

Example

Let's go through an example using the following sorted array:
arr = [2, 4, 7, 10, 15, 20, 25, 30, 35, 40]

Suppose we want to find the index of the target element 15:

Initialize left to 0 and right to 9 (the indices of the first and last elements in the array).

First iteration:
left=0
right=9
Calculate mid as (0 + 9) / 2 = 4.
Compare arr[4] (which is 15) with the target 15. They match, so we've found the target, and we return the index 4.
arr = [2, 4, 7, 10, 15, 20, 25, 30, 35, 40]
In this example, the binary search algorithm successfully located the target value 15 in just one iteration.

Let's go through an example where the target element is not present in the sorted array. We'll use the same sorted array as before:
arr = [2, 4, 7, 10, 15, 20, 25, 30, 35, 40]

Now, suppose we want to find the index of the target element 18. Here's how the binary search algorithm proceeds:

Initialize left to 0 and right to 9 (the indices of the first and last elements in the array).

First iteration:
left=0
right=9
Calculate mid as (0 + 9) / 2 = 4.
Compare arr[4] (which is 15) with the target 18. Since 18 is greater  than 15, update left to mid + 1, making left equal to 5.

Second iteration:
left=5
right=9
Calculate mid as (5 + 9) / 2 = 7.
Compare arr[7] (which is 30) with the target 18. Since 18 is smaller than 30, update right to mid - 1, making right equal to 6.

Third iteration:
left=5
right=6
mid=(5+6)/2=5
since arr[5] is 20 and 18 is smaller than 20 o update right=mid-1 so right=4.
Now, left is greater than right, which means the search interval has become empty. The loop terminates.

Since the loop has terminated and the target element 18 has not been found, the algorithm returns -1 to indicate that the element is not in the array.

In this example, the binary search algorithm correctly identifies that the target element 18 is not present in the sorted array. The algorithm efficiently eliminates half of the remaining elements in each iteration until it concludes that the element is not there.

Pseudo Code

int  binary_search(arr,n, target):
    left = 0
    right =n - 1

    while left <= right:
        mid = (left + right) / 2  # Calculate the middle index
        
        if arr[mid] == target:
            return mid  # Found the target, return its index
        elif arr[mid] < target:
            left = mid + 1  # Target is in the right half
        else:
            right = mid - 1  # Target is in the left half

    return -1  # Target not found in the array


Time Complexity:

Binary search is known for its efficiency in searching for elements in a sorted collection. The time complexity of binary search is O(log n), where 'n' is the number of elements in the sorted array. This means that the algorithm's runtime grows logarithmically with the size of the input data.

The reason binary search is so efficient is that it continually reduces the search interval by half with each iteration. As a result, even for very large arrays, it requires a relatively small number of comparisons to find the target element.

Space Complexity:

The space complexity of binary search is O(1), which means it uses a constant amount of extra memory regardless of the size of the input array. Binary search typically only requires a few variables to keep track of the current search interval and the middle index. It doesn't require additional data structures like arrays or lists, which is why it has a space complexity of O(1).

In summary, binary search is an extremely efficient algorithm for finding elements in a sorted array, with a time complexity of O(log n) and minimal space requirements (O(1)). It's an excellent choice for searching in large datasets where efficiency is a priority.

C Program - Binary Search
/*******************************************************************************/
#include <stdio.h>

int binarySearch(int arr[], int n, int target) {
    int left=0,right=n-1,mid;
    while (left <= right) {
        mid = left + (right - left) / 2;
        
        if (arr[mid] == target) {
            return mid; // Target found, return its index
        }
        
        if (arr[mid] < target) {
            left = mid + 1; // Target is in the right half
        } else {
            right = mid - 1; // Target is in the left half
        }
    }
    
    return -1; // Target not found
}

int main() {
    int i,n,arr[50],target,result;
printf("Enter number of elements :: ");
scanf("%d",&n);

printf("\nEnter %d elements in sorted order:: \n", n);
for ( i = 0 ; i < n ; i++ )
{
scanf("%d",&arr[i]);
}

printf("\nEnter key value to search :: ");
scanf("%d",&target);
result = binarySearch(arr, n, target);
    
    if (result != -1) {
        printf("Element %d found at index %d.\n", target, result);
    } else {
        printf("Element %d not found in the array.\n", target);
    }
    
    return 0;
}

/*******************************************************************************/
/* Recursive Implementation of Binary Search */
#include <stdio.h>

int binarySearch(int arr[], int left, int right, int target) {
    if (left <= right) {
        int mid = left + (right - left) / 2;

        if (arr[mid] == target) {
            return mid; // Target found, return its index
        }

        if (arr[mid] < target) {
            return binarySearch(arr, mid + 1, right, target); // Search in the right half
        } else {
            return binarySearch(arr, left, mid - 1, target); // Search in the left half
        }
    }

    return -1; // Target not found
}


int main() {
    int i,n,arr[50],target,result;
printf("Enter number of elements :: ");
scanf("%d",&n);

printf("\nEnter %d elements in sorted order:: \n", n);
for ( i = 0 ; i < n ; i++ )
{
scanf("%d",&arr[i]);
}

printf("\nEnter key value to search :: ");
scanf("%d",&target);
result = binarySearch(arr, 0,n-1, target);
    
    if (result != -1) {
        printf("Element %d found at index %d.\n", target, result);
    } else {
        printf("Element %d not found in the array.\n", target);
    }
    
    return 0;
}

Comments

Post a Comment

Popular posts from this blog

Data Structures CST 201 KTU Third Semester Syllabus Notes and Solved Questions- Dr Binu V P 984739060

Dr BinuV P -About Me About The Course Syllabus Data Structures Lab CSL 201 ( Do the Programs to Understand the Concept Well) Model Question Paper CST 201 Data Structures University Question Papers CST 201 Data Structures Module-1 Basic Concepts of Data Structures 1.1 System Life Cycle 1.2 Algorithms , Performance Analysis  1.3 Space Complexity, Time Complexity  1.4 Asymptotic Analysis and Notations  1.5 Complexity Calculation of Simple Algorithms Module-2 Arrays and Searching  2.1 Polynomial representation using Arrays  2.2 Sparse matrix  2.3 Stacks  2.4 Queues 2.5 Circular Queues  2.6 Priority Queues 2.7 Double Ended Queues 2.8 Infix to  Postfix Conversion  2.9  Evaluation of Postfix Expression 2.10 Linear Search  2.11 Binary Search Module-3 Linked List and Memory Management 3.1 Linked List -Self Referential Structures  3.2 Dynamic Memory Allocation  3.3 Singly Linked List-Operations on Linked List 3.4 Doubly Linked List 3.5 Circular Linked List  3.6 Stack using Linked List  3.7 Queue
Read more

Depth First Search DFS

Image
Depth-First Search (DFS) is a fundamental graph traversal algorithm that explores as far as possible along each branch before backtracking. It's often used to explore and analyze the connectivity of graphs, find paths, and solve problems related to connected components. Algorithm: The DFS algorithm operates on a graph, starting from an initial vertex. It maintains a stack (or uses recursion) to keep track of the vertices to visit. Initialization: Create a boolean array to mark visited vertices. Initialize all vertices as not visited. DFS Function: Choose a starting vertex (if the graph is disconnected, this process is repeated for unvisited vertices). Mark the chosen vertex as visited. Explore the chosen vertex's neighbours: If a neighbour is not visited, recursively call the DFS function on that neighbour. Repeat until all reachable vertices are visited. Here's a simplified recursive implementation in pseudocode: procedure DFS(vertex): mark vertex as visited for ea
Read more

Binary Search Tree ( BST) and operations

Image
A binary search tree (BST) is a data structure that organizes elements in a hierarchical structure, allowing for efficient search, insertion, and deletion operations. Here are the key properties and operations associated with a binary search tree: Properties of a Binary Search Tree: Binary Tree Structure:      Each node in the tree has at most two children: a left child and a right child.      The left subtree of a node contains only nodes with values less than the node's value.      The right subtree of a node contains only nodes with values greater than the node's value. Ordering Property:      For any node n , all nodes in its left subtree have values less than n, and all nodes in its right subtree           have values greater than n . No Duplicates:     A binary search tree does not allow duplicate values. Example: Figure  shows a binary search tree. Notice that this tree is obtained by inserting the values 13, 3, 4, 12, 14, 10, 5, 1, 8, 2, 7, 9, 11, 6, 18 in that order,
Read more