Skip to main content

Binary Search: Algorithms


Binary Search: Algorithms


What is Binary Search?


Binary Search is an interval searching algorithm used to search for an item in the sorted list. It works by repeatedly dividing the list into two equal parts and then searching for the item that is the part where it can possibly exist.

Unlike linear search, there are a few conditions for applying binary search:

  1. The list must be sorted.
  2. Random access to the list member.

It means that we cannot apply the binary search in unsorted or liked data structures.


Visualization of Binary Search:





Algorithm for Binary Search in C


Let [X] be the element we are searching for, and the array is sorted in the ascending order.

  1. Compare [X] with the middle element of the array.
     
  2. If [X] matches with the middle element, we return the index of the middle element.
     
  3. Else if [X] is greater than the middle element, it means that [X]
     can only lie in the right half subarray after the middle element. So, we repeat steps 1 and 2 for the right half subarray and leave the left half subarray from the algorithm
     
  4. Else if [X] is smaller than the middle element, it means that [X]
     can only lie in the left half subarray before the middle element. So, we repeat steps 1 and 2 for the left half subarray.
     
  5. We will keep doing that till we find [X] or there is no element left in the subarray being considered.

As we can see, the binary search ignores the half elements of the subarray after each pass. Due to this, it is able to reduce the time required for searching the element in the array as compared to linear search.


#include<stdio.h>

int binarySearch(int *arr, int size, int key){
    int start = 0;
    int end = size - 1;
    int mid = start+(end-start)/2;
   
    while (start <= end){
        if (arr[mid] == key){
            return mid;
        }

        if (key > arr[mid]){
            start = mid+1;
        }

        else{
            end = mid-1;
        }
        mid = start+(end-start)/2;
    }
    return -1;
}

int main(){

    int size,k;
    printf("Enter Size Of Array: ");
    scanf("%d",&size);

   
    int arr[size];
    printf("Enter Array Elements: ");
    for(int i=0;i<size;i++)
    {
        scanf("%d",&arr[i]);
    }
    printf("Enter Number To Find: ");
    scanf("%d",&k);
    int result = binarySearch(arr,size,k);
    printf("\n%d Found at Index: %d",k,result);
    return 0;
}



Output: 



Complexity Analysis of Binary Search (Iterative)

Time Complexity: O(log n), where n is the number of elements in the array.
Auxiliary Space: O(1)


 

Comments

Post a Comment

Popular posts from this blog

A Bridge Between Beginning & End

Welcome Back!  In the heart of our bustling city, where pollution in the surrounding and environment rush through concrete canyons, there exists a bridge a relic of the past, a thread connecting our urban fabric. Maya, a woman, walks this bridge every morning, her footsteps echoing against the worn-out pavement. The bridge spans a murky river, its iron railings rusted and chipped. As Maya steps onto it, she gazes at the surrounding buildings. They loom like silent sentinels, their windows cracked, graffiti defacing their once-pristine facades. These structures, once symbols of progress, now bear the scars of neglect. Maya's eyes sweep across the landscape. She notices the shattered glass of a bus stop, the faded murals on the walls, and the litter strewn about a testament to our collective disregard for public spaces. The bridge itself groans under the weight of years, its concrete pockmarked and crumbling. But Maya is not a passive observer. She carries a small bag a makeshift too...

Linked List - Data Structure

Linked List A linked list is a linear data structure that does not store elements in contiguous memory locations, the elements in the linked list are linked using pointers. It is a collection of nodes in which each node stores data and a pointer that links to the next node to form a sequence of nodes. -> Linked List is a linear data structure which is a combination of Nodes. -> Nodes contain two parts i.e. data & address. Representation of a Linked List in C: A linked list is represented as a pointer to the first node where each node contains: Data:  Here the actual information is stored. Next:  Pointer that links to the next node. Advantages of a Linked List: Linked list is dynamic data structure it has memory allocation and de-allocation, which means that memory is only used when needed and not earlier in order to avoid waste. In linked list items are arranged in a linear fashion, new items can be inserted or removed as and when needed without affecting other items...