**Binary search program in c** is simple and easy program.

Searching in Data Structures : In this tutorial we will study different **Searching Technique in Data Structures and Binary search program in c.**

**Searching Definition**

- The searching is a process of finding element in a data set of a data.
- There are huge data available (stored) and for finding data we required some technique so that we can access fast as possible within a minimum effort.

**Binary search**

- This is a another method for finding element in array.
- The condition for binary search is that all elements should be sorted we compare the element with the middle element of the array if it is less than a middle element then we search in a left portion of a array and if it is greater than the middle element then we search in right portion of array.
- Now we will take that the portion only for a search and compare with the middle element of that portion.
- This process will be in a iteration up till we find the element or a middle element that has no left or right portion to search.

**Binary search example **

Suppose, the element searching is 49

**Binary search**

**Iteration 1:-**

**Start=0 , end=9 , mid=start+end/2 (0+9/2=4)**

Now the element at a position **4** is **25** compare this with 49 that is **49>25**.

The middle element is smaller than finding element therefore our finding element is present in a right position of a array **so set start to mid+1.**

**start= mid+1**

**=> start= 4+1**

**so start= 5**

**Iteration 2:-**

In this, **Start = 5** and **end = 9**

Find, **mid= 5+9/2 =7**

But, **49<57**

In this case finding element is less than **mid** value, so we will find in left portion.

**end = mid-1**

** = 7-1**

** = 6**

**Iteration 3:-**

**Start = 5** and **end = 6**

Find, **mid= 5+6/2 = 5**

But, **49>30**

In this finding element is greater than middle element so we will find in right portion.

**Start = mid+1**

** = 5+1**

** = 6**

**Iteration 4:-**

**Start = 6** and **end = 6**

**mid= 6+6/2 = 6
**

6th is the position of 49 and it is mid value, We found the element 49 at 6 position in array.

In this way we can perform binary search now we will see the algorithm for Binary search.

**Binary search complexity**

Time complexity for linear search is log(N).

**Binary search algorithm**

1. Take a number of Array element user want.

2. next Take the array elements from user in ascending order only.

3. Take a finding element from a user.

4. Set start = 0 and end= last element of an array.

5. Then calculate a mid value = (Start+end/2)

6. Compare mid value with finding value.

7. Check mid value less than finding value if **yes** set **start to mid+1. **If not, Then set **end = mid -1.**

8. mid values and continue with step 6 until one mid value left (there is no left or right portion left)

9. If that one mid value is equal to finding element print **number found.**

10. If start > end print **number not found.**

11. Finish.

**Binary search program in c**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
#include <stdio.h> int main() { int c, first, last, middle, n, search, array[100]; printf("Enter number of elements\n"); scanf("%d",&n); printf("Enter %d integers\n", n); for (c = 0; c < n; c++) scanf("%d",&array[c]); printf("Enter value to find\n"); scanf("%d", &search); first = 0; last = n - 1; middle = (first+last)/2; while (first <= last) { if (array[middle] < search) first = middle + 1; else if (array[middle] == search) { printf("%d found at location %d.\n", search, middle+1); break; } else last = middle - 1; middle = (first + last)/2; } if (first > last) printf("Not found! %d isn't present in the list.\n", search); return 0; } |

**Output of program:**

**Explanation :**

**1. Declare variables.**

c => temporary variable

first => to store first index

last => to store last index

middle => to find middle of array

search > to store search element

array => array

**2. Take size of array**

scanf(“%d”,&n);

=> n=5

**3. Take array elements**

for (c = 0; c < n; c++)

scanf(“%d”,&array[c]);

=> array[] = 10,20,30,40,50

**4. Assign first index of to fist and last to last**

first = 0;

last = n – 1; => 4

middle = (first+last)/2; => middle = 2

**5. now search element in array from start to end**

**while (first <= last) => 0 < = 4 this condition true while block executed.**

if (array[middle] < search) => 30 < 20 this condition is false and if block skipped

else if (array[middle] == search) => this condition false

else last = middle – 1; => last = 1

middle = (first + last)/2; =>middle = 0 +1 /2 = 0

**while (first <= last) => 0 < = 1 this condition true while block executed.**

if (array[middle] < search) => 10 < 20 this condition is true and if block executed

first = middle + 1; => first = 1

else if (array[middle] == search) => this condition false

else last = middle – 1; => this condition false

middle = (first + last)/2; =>middle = 1 +1 /2 = 1

**while (first <= last) => 1 < = 1 this condition true while block executed.**

if (array[middle] < search) => 20 < 20 this condition is false

else if (array[middle] == search) => this condition true and else if executed

**now we found search element in array so print search element**

printf(“%d found at location %d.\n”, search, middle+1);

=> 20 found at location 2

**6. we found search element so no need to execute rest of the code so we write break**

break;

## Leave a Reply