Searching Algorithm in C | Linear VS Binary search

Hello everyone, Hope you all are doing good in your lives. In the universe of programming, it is usually said that coding helps the user to understand real-life problems more efficiently. And then the compiler of the computer comes into being and solves the problem for us. One of the first languages is C. Further in this blog, we are going to discuss the various searching algorithms in c programming. Their types? functioning, complexity! and much more.

Introduction to C

Icon of C programming languageAbove all C is a language develop at AT & T Bell Laboratory of the USA in the year 1972. However, it was written by a man Dennis Ritchie. Mainly in the 17th century, C began to replace all other main languages. Possibly the main reason for the fame of the C language can be the ease to use and understand. Moreover, in a CS or IT organization where new language, tools, and technology seem and vanish day in and time out. A language to survive over 3 decades has to be an extremely sensible

So now let’s jump into the main topic.

What is Algorithm?

However, an algorithm is a set of precise instructions for performing a Computation and or for solving a problem. Properties of the algorithm are Input, Output, Definiteness, Correctness, Finiteness, and Efficiency. whenever the program is quite long then it is to bisect up into various subprograms. The algorithm written for each subprogram is called a sub-algorithm. These are complete and independent modules. However, these modules are required to be called by the main algorithm or by any other sub-algorithm.

There are two main types of sub-algorithms

  1. Function sub algorithm( Returns 1 value at a time )
  2. Procedure sub algorithm(However these type can return more then one value at a time)

An example of an algorithm is;

Factorial of n

1. Start
2. Accept the number of which the factorial is to be calculated and store it in n
2. Initialize fact and n
3. Set the value of fact to 1
4. multiply the fact by number n and store the result back into fact
fact = fact * n
5. decrement n by 1 (n--)
6. Repeat step 3 and 4 until n becomes equal to 1
7. Give the final result stored in fact as factorial
8. Exit

The algorithm is written should be as simple as possible to understand by the user. this is because on this basis the main program or say the code of the problem is written.

Searching Algorithm in C

Linear Searching algorithm in C

Linear search is one of the simplest and easiest searching type algorithms. In this type, the key value is compared one by one with each and every element present in the array and if the match is obtained, then the output is yield as the index at which the key is present is otherwise the scan is continued till there is no element present in it. Linear search algorithm(searching and sorting algorithms in C))

In the above example, the key value is 12 which is to be searched in the array given above. Moreover, what happens here is the key is compared with the 0 indexes of the array and then consequently increased to the next index value until the match is obtained. In this case, the key is present at the 4th index. Thus the compiler will return this value and stop execution.

linear search algorithm

However,

Algorithm

Linear_search(Array(A[]),key)

1. Start
2. Set the pointer to the leftmost element of the  array
3. Initialize key and i
4. Accept the number from the user which is to be searched in the array and store it in Key
5. Now using For loop start traversing through all the elements of an array.
the test condition would be as follows, for(i=0, i<n, i++)
6. If the element is found then print the index at which the value is found
7. Else print element is not present
8. Exit

Whereas,

Pseudo code

Procedure Linear_search (Array(A[], Key)

start

  for each value present in the array
    if value==key
      print the index of the value
    end if
    else
      print key not found
  end for

stop

Complexity

Best case if the element is present at the 0 indexes. so the complexity of the search will be O(1). This is because in this only one comparison was require

Worst case if the element is absent in the array. However here the complexity becomes O(n). This is because here there are total n comparisons require.

Binary Searching algorithm in C

Binary search is an advance methodology of searching an element in an array. In this method, the array is cut into several halves at consecutive steps. However, in this method, the key is firstly compared with the middle term of the array and if the key is found then the index of the middle term is returned. on the other hand, if the match does not occur then it is checked that if the key is greater than the middle term or not if yes then the key is searched in the right half part of the middle term or else the left part of the middle term is scanned. This process works in a loop until the key is obtain or there is no element left in the array to go through.

Working of Binary Search

For a binary search to be effective we should have the array in order. Thus the figure below is a pictorial representation of the working of a binary search for finding 12. array of element to shoe binary searching algorithm in c

Firstly we shall find the midterm by using the formula lower index + (Upper index – lower index)/2array of element to shoe binary searching algorithm in c

Now the key is compare to the value of mid-term however both the values are not equal. On the other hand, the key is greater than the middle value, therefore, the left half of the array is now consider invalid.array of element to shoe binary searching algorithm in c

Here again, the midterm is obtain by using the same formula in the right half of the array here the lower index is 4 and the upper index is 7.array of element to shoe binary searching algorithm in c

Same as above the key is compare with the mid-term but this time also the there is no match. and the key is smaller than the value of mid-term therefore in this case the right half becomes the invalid region.array of element to shoe binary searching algorithm in c

Again the midterm is obtain with the help of formula and this time the key and the mid-term are equal to each other and hence the index of the mid-term is obtain as output and the execution comes to end.

Algorithm

Binary_search (A[],Key)

1. Start
2. Set one pointer to the starting element of the array and one pointer to the last element to the array
3. Find the midpoint by using the first and last pointer
4. Compare the key with the value of mid point
5. If the key is equal to the midpoint then print the index and stop the program
6. If the key value is greater then the mid term then the first pointer is set to the next index of the mid term
7. If the key is less than the mid term then the last pointer is set to the index just before the mid term
8. Continue step after 3 until the key is found or there is no element left in the array to compare to
9. Stop

However,

Pseudo Code

Procedure Binary_Search (A[], Key)
lower pointer = i
upeer pointer = j

Start

  Set i = 0
  Set j = 9
  
  While (i<=9)
    mid = lower + (upper-lower)/2

    if A[mid] == key
      print the index of the mid point
    End if

    Else if A[mid]>Key
      j = mid-1
    End Else if

    Else
      i = mid+1
    End else

  If(i>9)
    print element not found
  End If

Stop

Complexity

The best-case key is present at the middle of the array. So the complexity will be O(1). This is because only one comparison was needed.

Worst case key is not a part of the array. So the complexity becomes O(log2n). This is because in this method the array is pair down to 1 value by halving the array n time

n, n/2, n/22, n/23,…………………….n/2m

∴n/2m = 1

∴m = log2n

Conclusion

Consequently here we are to the last and the foremost part of the blog. I hope that you are now all clear and are satisfied with the content above. If you like the blog then please do comment and share it with others. Besides, feel free to ask any doubts I have regarding the topic.

Have a nice day 🙂

Regards.

Read More

  1. What is AM Transmission and Reception?
  2. 6 Jaw-dropping Applications of Combinational logic Design
  3. Top 7 bizarre Applications of Mosfet |and its features
  4. Logic Families and its Features| TTL Vs CMOS
  5. What is a DC Machines?- DC Motors OR DC Generator.
  6. ALL ABOUT COMMUNICATION SYSTEM.
  7. MOSFET (Construction, Working and Characteristic)
  8. Control System(Features, Types etc)

2 Comments

  • Yash March 25, 2021 at 5:11 pm Reply

    Amazing write up!

  • Shivam March 25, 2021 at 5:15 pm Reply

    Mast👌

Leave a Comment