Limited Period Offer : 20% Discount on online/offline courses, for more details call/whatsapp

Searching Algorithm.

2 min read
2 years ago By Aniket Prajapati

Searching Algorithm.

In an Array based on the type of search operation, these algorithms are generally classified into two categories: (1) Linear Search. (2) Binary Search.

(1) Linear Search :

In this, the list or array is traversed sequentially and every element is checked.

Code:

`// code for linear Search

#include<bits/stdc++.h>
using namespace std;

**// this function has argument as array and int which we need to search and if fount it returns its index else it returns -1.**
int linear_search(int arr[10],int x)
{
    for(int i=0;i<10;i++)
    {
        if(arr[i]==x)
        {
            return i;
        }
    }
    return -1;
}
int main()
{
    int arr[10];
    int x;
    for(int i=0;i<10;i++)
    {
        cin>>arr[i];
    }
    cin>>x;
    int ans=linear_search(arr,x);
    cout<<ans;
    return 0;
    
}`

Time Complexity: O(N). ,where N is the number of elements in the array/list

**Binary Search **:

Binary Search is defined as a searching algorithm used in a sorted array by repeatedly dividing the search interval in half. The idea of binary search is to use the information that the array is sorted and reduce the time complexity to O(log N).

Algorithm : (1) Divide the search space into two halves by finding the middle index “mid”. (2) finding the middle index "mid" in Binary Search Algorithm (3) Finding the middle index “mid” in Binary Search Algorithm

Compare the middle element of the search space with the key. If the key is found at middle element, the process is terminated. If the key is not found at middle element, choose which half will be used as the next search space. If the key is smaller than the middle element, then the left side is used for next search. If the key is larger than the middle element, then the right side is used for next search. This process is continued until the key is found or the total search space is exhausted.

Code :

// C program to implement iterative Binary Search #include <stdio.h>

// An iterative binary search function. int binarySearch(int arr[], int l, int r, int x) { while (l <= r) { int m = l + (r - l) / 2;

	// Check if x is present at mid
	if (arr[m] == x)
		return m;

	// If x greater, ignore left half
	if (arr[m] < x)
		l = m + 1;

	// If x is smaller, ignore right half
	else
		r = m - 1;
}

// If we reach here, then element was not present
return -1;

}

// Driver code
int main(void)
{
	int arr[] = { 2, 3, 4, 10, 40 };
	int n = sizeof(arr) / sizeof(arr[0]);
	int x = 10;
	int result = binarySearch(arr, 0, n - 1, x);
	(result == -1) ? printf("Element is not present"
							" in array")
				: printf("Element is present at "
							"index %d",
							result);
	return 0;
}

to practice the questions : https://practice.geeksforgeeks.org/problems/binary-search-1587115620/1?utm_source=gfg&utm_medium=article&utm_campaign=bottom_sticky_on_article

Jun 23, 2023 21:03 Back to Articles

Other Articles

Introducing ECMAScript 6 (ES6): A New Era for JavaScript Development Introducing ECMAScript 6 (ES6): A New Era for JavaScript Development

In this article, we'll explore the important changes and improvements that came with ECMAScript 6 (ES6), and how they've made JavaScript programming better.

1 year ago By Mitali Gupta
React State Management Made Easy: Zustand and Redux Explained React State Management Made Easy: Zustand and Redux Explained

In this article, we will discover two powerful state management libraries for React: Zustand and Redux. Also explore their unique approaches, advantages, and use cases, to simplify and optimize your application's state handling. Choose the best fit for your project's needs and boost development efficiency with these popular solutions.

1 year ago By Mitali Gupta
Merge Two Sorted Linked List

Merge Two Sorted Linked List is a Standard Linked list Problem which is Frequently asked in Many Coding interviews. The basic idea is you have given Two Sorted Linked list which are sorted in its own and you have to return return a pointer node which has a merge single list of both the sorted list .

1 year ago By Aniket Prajapati
Prim's Algorithm

Prim's Algorithm is a graph algorithm and this algorithm works as it starts with a single node and then moves through several adjacent nodes form that node , in order to explore all of the connected edges along the way.

2 years ago By Aniket Prajapati