Binary search program in C/C++

Binary search program in C/C++

Binary search is an efficient algorithm for finding an item from a sorted list of items. The time complexity of above algorithm is O(n). Search a sorted array by dividing the search interval in half repeatedly. If the value is less than the item in the middle of the interval, narrow the interval to the lower half. Otherwise narrow it to the upper half. Check until the value is found or the interval is empty. We will see a program of binary search in C/C++.

Q. Write a program in C and C++ to implement Binary Search.

1. Program in C

#include<stdio.h>
int i, j, s, temp, top, bot, mid;
int a[10];
int main() {
  void print(int[]);
  void sort(int[]);
  void search(int[]);
  printf("\n Enter 10 elements: ");
  for (i = 0; i < 10; i++)
    scanf("%d", & a[i]);
  printf("\n Original array: ");
  print(a);
  printf("\n Sorted array: ");
  sort(a);
  print(a);
  search(a);
  return 0;
}

void print(int a[]) {
  for (i = 0; i < 10; i++) {
    printf("%d ", a[i]);
  }
}

void sort(int a[]) {
  for (i = 0; i < 10; i++) {
    for (j = i + 1; j < 10; j++) {
      if (a[i] > a[j]) {
        temp = a[i];
        a[i] = a[j];
        a[j] = temp;
      }
    }

  }
}

void search(int a[]) {
  printf("\n Enter number to be searched: ");
  scanf("%d", & s);
  top = 0;
  bot = 9;
  mid = (top + bot) / 2;
  while ((top <= bot) && (a[mid] != s)) {
    if (s < a[mid]) {
      bot = mid - 1;
    } else {
      top = mid + 1;
    }
    mid = (top + bot) / 2;
  }
  if (a[mid] == s) {
    printf("\n Number is at position %d", mid + 1);
  } else {
    printf("\n Not found");
  }
}

2. Program in C++

#include<iostream>
using namespace std;
int i, j, s, temp, top, bot, mid;
int a[10];
int main() {
  void print(int[]);
  void sort(int[]);
  void search(int[]);
  cout << "\n Enter 10 elements: ";
  for (i = 0; i < 10; i++)
    cin >> a[i];
  cout << "\n Original array: ";
  print(a);
  cout << "\n Sorted array: ";
  sort(a);
  print(a);
  search(a);
  return 0;
}
void print(int a[]) {
  for (i = 0; i < 10; i++) {
    cout << a[i] << "  ";
  }
}

void sort(int a[]) {
  for (i = 0; i < 10; i++) {
    for (j = i + 1; j < 10; j++) {
      if (a[i] > a[j]) {
        temp = a[i];
        a[i] = a[j];
        a[j] = temp;
      }
    }
  }
}

void search(int a[]) {
  cout << "\n Enter number to be searched: ";
  cin >> s;
  top = 0;
  bot = 9;
  mid = (top + bot) / 2;
  while ((top <= bot) && (a[mid] != s)) {
    if (s < a[mid]) {
      bot = mid - 1;
    } else {
      top = mid + 1;
    }
    mid = (top + bot) / 2;
  }
  if (a[mid] == s) {
    cout << "\n Number is at position " << mid + 1;
  } else {
    cout << "\n Not found";
  }
}

3. Output-

Binary search output

4. Explanation-

In this program we use functions. Thus we declare three function, each function will perform separate task. First print function will print the array. Sort function will sort the unsorted array. And search function will search an element in the array,

In main function we first declare our three functions. Then we ask user to enter array elements. Here we are accepting maximum 10 elements. After accepting all elements we print original array. And then we print sorted array by calling sort() function. In sort function definition elements are sorted in ascending order.

In search() function we ask user to enter an element that he wants to search. Here we use three variables top, bot, mid. Top stores first index of array and bot stores last index of array and mid stores middle index of array. Now the number that user has entered is compared with mid element of array. If the number to be searched is smaller than middle element then searcing takes place between top to mid index. Else searching takesplace between mid to bot index.

The value of top, bot and mid changes depending upon the number to be searched. The loop executes continuously till the value of number to be searched is equal to the value of arr[mid]. If the number is found then the location of number is printed else number not found is printed.

5. Parts of program-

1. #include is a pre-processor directive. It is used to include header files.
2. stdio/iostream is header file which has certain commands that c/c++ supports. E.g. return, main, etc.
3. .h is an extension for header file.
4. int is data type. It indicates that the program returns a value.
5. main() is main function that indicates the compiler that the user written programs starts from here.
6. print/cout is the keyword use to print a message.
7. scanf/cin is the keyword use to store values in variables.
8. return statement is use to return a value. If any error occurs the program will return 0.

Conclusion-

This was the program of Binary search in C/C++. We hope it was clear to you. If you find it useful then do share it with your programming buddies and friends. Also if you have any doubt regarding any post do tell us in the comment section.

For daily updates do follow us on Instagram. Visit again!

ErrorFreeProgram.

Leave a Reply

Your email address will not be published. Required fields are marked *