Question

In: Computer Science

Typed please.How can we implement efficient search operations? In this area, we will discuss various algorithms,...

Typed please.How can we implement efficient search operations? In this area, we will discuss various algorithms, including sequential search, sorted search, and binary search. The characteristics of these algorithms will be analyzed, such as the running times and the type of lists they can be used with.

Solutions

Expert Solution

If we write a computer program to perform some task we need implement a suitable algorithm. There are so many algorithms are there to perform same task but we have to choose the best algorithm that should work very efficiently. We can calculate if a program is efficient or not by using time complexity and space complexity. These two are basic measure to know which one is an efficient algorithm. suppose if an algorithm has best time complexity when compared to some other algorithms then we can say that particular algorithm is efficient for search operations.

1. sequential search: it is also called linear search. in this we have to take an element to search. compare that element with each number in sequential manner. like wise we have to compare element with all other elements. if a number is found exit from the program otherwise continue the process till the end of list and exit.

example: we have list of numbers

20 95 87 12 78 65 25 3

now search for a number 87

compare 87 with 20 that is  if(87==20) match is not found, now courser will move to next number

compare 87 with 95 again match is not found , now move to next number

compare 87 with 87 yes match is found, finally output will be printed. like this we have compare.

2. sorted search: In sorted search we have to take array with sorted manner. either from ascending order or descending order. now take one number and compare with each element. if the element is found at a location then the output will be the index of particular element otherwise it exits from the program.

for example lets take an array with sorted elements

array{ -4, -3,0,4,11,65,76,87}

search for an element 11

compare 11 with -4 match not found

compare 11 with -3 match not found

compare 11 with 0 match not found

compare 11 with 4 match not found

compare 11 with 11 match found,. so the output will be the index of that number

output is: 4 [ 11 is placed at 4 th location]

if suppose compare 5

compare 5 with each element 5 is not matched with any element so it will exit from the program.

3. binary search: Binary search is simple complex than remaining algorithms but very quickly it gives the efficient search operation. first it takes a list of sorted array. take a mid point by counting the num of elements. first element is lowest point and last element highest point ,middle element is mid point.

example: if we have 8 elements {5,18,26,54,96,102,156,170} take mid point that is 8/2=4

so 4 is the mid point

L=0 mid=4 H=7   

5 18 26 54 96 102 156 170

so the mid point value is 54

our search element is 18, compare 18 with mid value 54 (54>18) 18 is a smaller than 54 so 18 is placed in left side of the mid point.

now compare 18 with left sub tree of element 5 match not found

now compare 18 with 18 yes match found so that out will the position of the element that is 2nd position

Among all these algorithms binary search operation is very efficient because searching time reduced when compare to other algorithms. Based on the condition we can easily identify the element is placed in left or right of the sub tree. the time complexity of binary search is O(logn)

In sequential search we have to search till the end of the list. it take longer process when we have large list.

In sorted search also we have to search till the end of the list. it is also not suitable for longer list of arrays.

binary search is an efficient search algorithm, it reduces the searching time.


Related Solutions

(Python or C++) We are going to implement the following scheduling algorithms that we discussed in...
(Python or C++) We are going to implement the following scheduling algorithms that we discussed in class: 1. First-Come First-Served (FCFS) 2. Shortest Remaining Time First (SRTF) 3. Highest Response Ratio Next (HRRN) 4. Round Robin, with different quantum values (RR) We are interested to compute the following metrics, for each experiment: _ The average turnaround time _ The total throughput (number of processes done per unit time) _ The CPU utilization _ The average number of processes in the...
Run an Effective and Efficient Search Committee for an event management company. How can we actively...
Run an Effective and Efficient Search Committee for an event management company. How can we actively recruit an Excellent and Diverse Pool of Candidates for an event management company?
Run an Effective and Efficient Search Committee for an event management company. How can we actively...
Run an Effective and Efficient Search Committee for an event management company. How can we actively recruit an Excellent and Diverse Pool of Candidates for an event management company?
We can implement a basic web search engine by building an inverted index (also known as...
We can implement a basic web search engine by building an inverted index (also known as an index) that maps each term (word) to the set of web pages in which it appears. A search query, which is a sequence of one or more keywords, can be answered by returning the web pages that contain all of the terms in a given query. Implement a JAVA SearchEngine class that represents an inverted index. 1) SearchEngine() Constructs an empty SearchEngine instance....
Tasks 2 Write algorithms in pseudocode to implement a LinkedList The following operations must be performed...
Tasks 2 Write algorithms in pseudocode to implement a LinkedList The following operations must be performed on the LinkedList: *Add an element *Insert an element at a given position x. *Retrieve/Read the value of an element at position y. *Delete an element from position z. (x,y and z represent any value in the valid range of indices of the LinkedList).
1) Discuss the complexity of building efficient algorithms in Game Theory (+150 words)
1) Discuss the complexity of building efficient algorithms in Game Theory (+150 words)
Lab 5: Binary Search Tree Implement operations for a Binary Search Tree class starting from the...
Lab 5: Binary Search Tree Implement operations for a Binary Search Tree class starting from the template provided under the PolyLearn assignment, using the class TreeNode that is also provided. You may (should) implement helper methods that make your code easier to write, read, and understand. You will also need to write test cases of your own as you develop the methods. You may use iterative and/or recursive functions in your implementation. The following starter files are available . •...
In MobaXterm, with the use of the binary search tree. Implement four operations of insert, in-order...
In MobaXterm, with the use of the binary search tree. Implement four operations of insert, in-order traversal, preorder traversal, and find. Please separate the code in the four parts and explain in detail what is happening. Also, if you can please basic C language. If not, then I understand. Thank you for your time. The test cases are 'm', 'd', 'g', 'r', 'p', 'b', and 'x'. Output: Enter choice (lower case is also acceptable) --- (I)nsert, (F)ind, (Q)uit: i Enter...
Binary Tree Develop algorithms for performing various operations of binary tree like insertion and deletion of...
Binary Tree Develop algorithms for performing various operations of binary tree like insertion and deletion of elements, finding an element in the binary tree. Analyse time and space complexity of the designed algorithm Write C++ program to implement binary tree
How do we define the stack ADT, including its operations? Typed please.
How do we define the stack ADT, including its operations? Typed please.
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT