1.2.10
Binary Search
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.
1Computational Thinking & Algorithms
1.1Computational Thinking
1.2Algorithms
1.2.1Algorithms
1.2.2Pseudocode
1.2.3Flow Diagrams
1.2.4Logical Reasoning & Debugging
1.2.5Reading Algorithms
1.2.6Correcting Algorithms
1.2.7Complete the Algorithm
1.2.8Search Algorithms
1.2.9Linear Search
1.2.10Binary Search
1.2.11Sort Algorithms
1.2.12Bubble Sort
1.2.13Insertion Sort
1.2.14End of Topic Test - Algorithms
2Programming
2.1Programming Fundamentals
2.1.1Variables & Constants
2.1.2Comments
2.1.3Input & Output
2.1.4Arithmetic Operators
2.1.5Relational Operators
2.1.6Boolean Operators
2.1.7Sequence
2.1.8Selection
2.1.9Iteration
2.1.10Subroutines
2.1.11Scope
2.1.12Data Types
2.1.13Casting
2.1.14Arrays
2.1.152D Arrays
2.1.16Lists
2.1.172D Lists
2.1.18Strings
2.1.19Syntax Errors
2.1.20Logic Errors
2.1.21Runtime Errors
2.1.22End of Topic Test - Programming
2.2Designing Code
3Hardware & Software
3.1Hardware
3.2Software
4Data
5The Internet
6Online Safety & Security
6.1Protecting Yourself Online
Jump to other topics
1Computational Thinking & Algorithms
1.1Computational Thinking
1.2Algorithms
1.2.1Algorithms
1.2.2Pseudocode
1.2.3Flow Diagrams
1.2.4Logical Reasoning & Debugging
1.2.5Reading Algorithms
1.2.6Correcting Algorithms
1.2.7Complete the Algorithm
1.2.8Search Algorithms
1.2.9Linear Search
1.2.10Binary Search
1.2.11Sort Algorithms
1.2.12Bubble Sort
1.2.13Insertion Sort
1.2.14End of Topic Test - Algorithms
2Programming
2.1Programming Fundamentals
2.1.1Variables & Constants
2.1.2Comments
2.1.3Input & Output
2.1.4Arithmetic Operators
2.1.5Relational Operators
2.1.6Boolean Operators
2.1.7Sequence
2.1.8Selection
2.1.9Iteration
2.1.10Subroutines
2.1.11Scope
2.1.12Data Types
2.1.13Casting
2.1.14Arrays
2.1.152D Arrays
2.1.16Lists
2.1.172D Lists
2.1.18Strings
2.1.19Syntax Errors
2.1.20Logic Errors
2.1.21Runtime Errors
2.1.22End of Topic Test - Programming
2.2Designing Code
3Hardware & Software
3.1Hardware
3.2Software
4Data
5The Internet
6Online Safety & Security
6.1Protecting Yourself Online
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