8.1.4
Search Algorithms
Search Algorithms
Search Algorithms
Searching is a classic computer science problem. It involves finding a certain value in a set of other values.
Search algorithms
Search algorithms
- A search algorithm is a set of instructions for finding a specific item of data within a data set.
- Computer systems can store and process billions of pieces of data so it is vital that computers can find the information they need efficiently.
Effective searching
Effective searching
- An effective search is one which will always either find the solution or determine that the target data is not present.
Efficient searching
Efficient searching
- An efficient search will find the solution quickly regardless of its location within the data set.
Examples of search algorithms
Examples of search algorithms
- Two common search algorithms are:
- Linear search.
- Binary search.
Linear Search
Linear Search
Linear search is one of the simplest searching algorithms.
The concept
The concept
- If you were looking for a specific piece of paper in a stack of papers, then one way to find it would be to work from the top of the stack to the bottom, checking each paper on the way.
- This is exactly how linear search works.
In English
In English
- Check the first item in the dataset:
- If it is what we are looking for, return it.
- Check the second item in the dataset:
- If it is what we are looking for, return it.
- Continue for rest of items.
- If we reach the end of the data set, then the item was not in our data set.
,h_400,q_80,w_640.png)
Pros and cons of linear search
Pros and cons of linear search
- Pros:
- Very easy to implement.
- Cons:
- Slow on a long list.
Binary Search
Binary Search
Binary search is an example of a divide-and-conquer algorithm.
The concept
The concept
- If you try to find a certain page in a book, it's unlikely that you check every page on the way.
- You are more likely to split the book in two, then see if the page you need is before or after the split, and repeat.
- This is the concept behind the binary search.
In English
In English
- Find the middle of the dataset.
- If the middle value is greater than the target then:
- Repeat on the first half of dataset.
- If the middle value is lesser than the target then:
- Repeat on the second half of dataset.
- If the middle value is the target:
- We found it!
- Stop repeating once the size of our dataset is zero.
Pros and cons of binary search
Pros and cons of binary search
- Pros:
- Faster than linear search on a large dataset.
- Cons:
- Dataset must be sorted before starting.
1Components of a Computer
1.1Structure & Function of the Processor
1.2Types of Processors
2Software & Software Development
2.1Systems Software
2.2Applications Generation
2.3Software Development
3Exchanging Data
3.1Compression, Encryption & Hashing
3.3Networks
4Data Types, Data Structures & Algorithms
4.1Data Types
5Legal, Moral, Cultural & Ethical Issues
5.1Computing Related Legislation
6Elements of Computational Thinking
6.1Thinking Abstractly
6.2Thinking Procedurally
6.3Thinking Logically
7Problem Solving & Programming
7.1Programming Techniques
7.2Programming Construction
Jump to other topics
1Components of a Computer
1.1Structure & Function of the Processor
1.2Types of Processors
2Software & Software Development
2.1Systems Software
2.2Applications Generation
2.3Software Development
3Exchanging Data
3.1Compression, Encryption & Hashing
3.3Networks
4Data Types, Data Structures & Algorithms
4.1Data Types
5Legal, Moral, Cultural & Ethical Issues
5.1Computing Related Legislation
6Elements of Computational Thinking
6.1Thinking Abstractly
6.2Thinking Procedurally
6.3Thinking Logically
7Problem Solving & Programming
7.1Programming Techniques
7.2Programming Construction
Unlock your full potential with GoStudent tutoring
Affordable 1:1 tutoring from the comfort of your home
Tutors are matched to your specific learning needs
30+ school subjects covered