Binary Search

Binary Search

The method is based on the Divide-Conquer algorithmic strategy.

• Precondition For Binary Search

1. Data must be organized in a linear way.
2. Data has to be in the sorted oder in either ascending or decending order.

• Advantages of Binary Serach

1. Worst case time complexity is O(log2n), which is very efficient compared to linear search O(n).

• Disadvantages of Binary  Search

1. Data has to be in sorted order.

• Complexity of Binary Search

Best Case:-The key is found at the middle position after 1 comparision.

                  -The best case time complexity is Ω(1).

Worst Case:-The Worst case time complexity is O(log2n).

CODE

👇

1. #include <stdio.h>
2. int main()
3. {
4.       int first, middle,last, n, i, search, a[100];
5.       setbuf(stdout, NULL);
6.       printf("ENTER THE SIZE OF ARRAY:");
7.       scanf("%d", &n);
8.       printf("ENTER %d ELEMENT IN ASCENDING ORDER:\n",n);
9.       for(i=0; i<n; i++)
10.           scanf("%d", &a[i]);
11.           printf("ENTER THE VALUE TO BE SEARCH:\n");
12.           scanf("%d", &search);
13.           first=0;
14.           last=n-1;
15.           middle=(first+last)/2;
16.           while(first <= last)
17.           {
18.                 if(a[middle]<search)
19.                 first = middle + 1;
20.                 else if(a[middle] == search)
21.                 {
22.                       printf("ELEMENT FOUND AT INDEX %d.\n",middle);
23.                       break;
24.                 }
25.                 else
26.                     last = middle - 1;
27.                     middle = (first + last)/2;
28.            }
29.                  if(first > last)
30.                  printf("ELEMENT NOT FOUND IN THE LIST.\n");
31.                  return 0;
32. }

👉Execute👈

//Output

/*

1]

ENTER THE SIZE OF ARRAY:5

ENTER 5 ELEMENT IN ASCENDING ORDER:

1

3

5

7

9

ENTER THE VALUE TO BE SEARCH:

5

ELEMENT FOUND AT INDEX 2.

2]

ENTER THE SIZE OF ARRAY:5

ENTER 5 ELEMENT IN ASCENDING ORDER:

1

3

5

7

9

ENTER THE VALUE TO BE SEARCH:

8

ELEMENT NOT FOUND IN THE LIST.

*/

                                                                                               //ThE ProFessoR