Please login

Prime

Prepinsta Prime

Video courses for company/skill based Preparation

(Check all courses)
Get Prime Video
Prime

Prepinsta Prime

Purchase mock tests for company/skill building

(Check all mocks)
Get Prime mock

Binary Search in C

Binary Search in C

Binary search is very fast and efficient searching algorithm. It requires to be list be in a sorted order, ie; either in ascending or descending.In this method, to search an element you might compare that respective element present in the center of the list and if it’s same then the search is successfully finished and if not, then the list is  divided into two parts:one from 0th element to the centered element and other from the centered element to the last element.

Binary Search
Time Complexity (Best) Ω(1)
Time Complexity (Avg) Θ(log n)
Time Complexity (Worst) O(log n)
Space Complexity O(1)

How Binary Search in C works?

  1. The searching algorithm proceed from any of two halves
  2. Depends upon whether the element you are searching is greater or smaller than the central element
  3. If the element is small then, searching is done in first half
  4. If it is big then searching is done in second half. 

It is fast search algorithm with the complexity of O(log n).

Binary Search in C Intro

Implementation of Binary Search

  • Step  1- In the Given array, first you need to find the middle of the list using formula mid=(min+max)/2.
  • Step 2-If the searched element ie; say 15(in context with the image given below) is in the centered then the search is terminated, as we can see here it is not.
  • Step 3- With the help of this algorithm we will try to find the value. first of all you have to defined two variable low and high so low is 3 and high is 22. Now you have to find the mid element.so we will find the mid value of the formula.
  • Step 4- We would know that in which half the searching would be done.
  • Step 5- So we would go for the second half as the searching element i.e; 15 is greater than the mid element i.e 12.
  • Step 6- The process repeat on until we find the element.
Binary Search in C
Binary Search in C Example

Algorithm of Binary Search

Step 1- while low < high
            do mid <-(low+high)
Step 2- if V=A[mid]
             return mid
Step 3- if V=A[mid]
           low<- mid+1
Step 4- else high<- mid-1
Step 5- return Nil

Program of Binary Search

#include<stdio.h>   //header files

int binarySearch(int[], int, int, int); int main() //main function {
int arr[10] = {9, 26, 33, 47, 53, 60, 75, 80, 86, 99}; int item, location = -1; printf("Enter the item which you want to find "); scanf("%d",&item); location = binarySearch(arr, 0, 9, item); if(location != -1) //looping logic { printf("Item found at location %d",location); //printing the element } else { printf("Item not found"); } return 0; } int binarySearch(int a[], int start, int last, int item) { int mid; if(last >= start) { mid = (start + last)/2; if(a[mid] == item){ return mid+1; } else if(a[mid] < item){ return binarySearch(a,mid+1,last,item); } else{ return binarySearch(a,start,mid-1,item); } } return -1; }
Output:-
Enter the item which you want to find 26 
Item found at location 2
Enter the item which you want to find 3
Item not found
Binary Search in C Meme

Time Complexity
For Binary Search

Best

O(1)

Average

O(log n)

Worst

O(log n)

Space Complexity

O(1)

Average Comparisions

Log(N+1)

Quiz time

Quiz Time

Question 1.Binary search algorithm can’t be applied to

  1. Pointed Array List
  2. Sorted Binary Tree
  3. Unordered Array
  4. Sorted Linked List

(Cisco, Walmart Labs)

You cannot use a binary search on an unsorted list. Your best bet is to probably iterate over the list’s items until you find the element you are looking for, an O(n) operation, i.e. do linear search

Ans. C

Question 2. Which is the following searching algorithms works on the divide and conquer?

  1. Binary Search
  2. Linear
  3. Sequential
  4. Merge Sort

(CoCubes, Atos Syntel)

Binary search only checks the middle element of the array. when it checks the middle element and middle element is not equal to the given element then we divide the list in two subparts.

Ans: Both A & D

Data Structures and Algorithm Learn Searching PrepInsta

Searching

Searching algorithms are easy to learn but are really important for college semester exams and companies offering package between 3 – 6 LPA would ask direct searching questions in online test/ interviews.