Guide to High School Computer Science
  • 💻Introduction
    • windows & Python Development
    • macOS & Python Development
    • Visual Studio Code Settings
    • Set up Github
    • Author Page
  • 🧠Prerequisite Skills
    • Keyboard Typing
    • Files & Directories
    • Use of Command Line
    • Git & GitHub
    • Markdown
    • Starting Your Python Project
  • 🐍Python Programming
    • 🍎Python Basics
      • What is Python?
      • Procedural Programming & Programming Paradigms
      • String Formatting
      • Data Types
      • Input & Output to Console
      • Working with Numbers
      • Useful Built-in Functions
      • Math & Random Module
      • Boolean Data Object
      • Comparison, Logical, and Membership Operators
      • If Statements
      • Binary Decisions
      • Multiple Decisions
      • Nested Conditions
      • [EXTRA] Bitwise Operators
      • [EXTRA] Python Style Guide
    • ⏮️Iterations
      • Introduction to While Loops
      • Infinite Loop
      • Controlling Your While Loops
      • Introduction to For Loops
      • For Loops w/ Numeric Sequences
      • For Loops w/ Strings & Lists
      • Iterable Functions w/ For Loops
    • 📦Collections
      • Strings
        • String Basics
        • String Indexing
        • String Slicing
        • String Operators & Functions
        • Basic String Methods
        • String Methods Extended
        • String Methods Document
      • Tuples & Lists
        • Tuples
        • List Basics
        • List are Mutable
        • Adding Items to a List
        • Removing Items from a List
        • Search & Reverse a List
        • List Comprehension
        • List Methods Document
      • Sets
      • Dictionary
      • How to Store Multiple Data Items
    • 💡Defining Functions
      • Functions
      • print() vs return
      • Pre-determined Arguments
      • Nested Functions
      • Map & Filter
      • [Extra] Dynamic Arguments
    • 💾File I/O
      • How to Save Text to an External File
      • Reading CSV in Python
      • Reading JSON in Python
    • 🔨Basic Python Projects
      • Basic Calculator
        • Improving the calculator
        • Exercise Set 1
        • Exercise Set 2
        • 💎Streamlit Application #1
      • Basic Password Generator
        • Exercise Set 3
        • Exercises Related to Math
        • 💎Streamlit Application #2
      • A To-Do Task List
    • ⏳Introduction to Algorithmic Thinking
      • Big-O Notation
      • Basic Algorithms
        • Linear Search
        • Binary Search
        • Basic Sorting Algorithms
      • Recursion
      • Brute Force Algorithms
      • Greedy Algorithm
        • Time on Task (CCC 2013 J4)
        • Dijkstra’s Algorithm
      • Divide and Conquer
        • Merge Sort
      • Dynamic Programming
    • 🤯Object Oriented Programming
      • Class & Objects (Definitions)
      • OOP in Python
      • Encapsulation
      • Polymorphism
      • Inheritance & Overriding
      • Override Magic Methods
      • Case Study: 2D Vectors
      • Case Study: Deck of Cards
      • Exercise
      • Abstract Data Types
      • Case Study: Static 1D Array From Java
    • Competitive Programming
      • Is This Sum Possible?
        • Is the dataset sorted?
        • Searching for a value
        • Determine if the difference between an integer from the array and the target value exists
        • Sorting Algorithms
        • Using Two Pointers
      • Two Sum - LeetCode
        • Generate all possible pairs of values
        • Subtract each value from the target, see if the difference exists in the list
      • Longest Common Prefix - LeetCode
        • Compare all possible prefixes
        • Create the longest common prefix with the direct neighbour
      • Length of Last Word - LeetCode
        • Compare all possible prefixes
      • Where can I go from one point to another?
      • Sample Outline
    • IB Recipe Book
  • 💾Python & Databases
    • Intro to Databases & Data Modeling
      • Common Data Types in SQL
      • Introduction to ERDs
      • Primary Keys and Foreign Keys
      • Database Normalization
    • What is SQL?
      • Getting Started
      • SELECT Queries
        • Selection with Conditions
        • Selection with Fuzziness
        • Selection and Sorting in Order
        • Selection without Duplicates
        • Selection with Limited Number of Outputs
      • AGGREGATE Queries
        • Counting Rows
        • Sum, Average, Min/Max Queries
        • Working with Aggregate Queries
        • Power of using Groups
        • Exercise
      • Interacting with Multiple Table
      • Inserting Data
      • External Resource
  • ☕Java Essentials
    • Basics
      • Starting Java
      • Data & Variables
      • Handling User Inputs & Type Conversion
      • Arithmetic
      • IPO Model
      • Basic Built-in Methods
      • Exercise Questions
    • Conditionals
      • Boolean Operators
      • Compare Strings
      • If Statements
      • If Else Statements
      • Making Multiple Decisions
      • Using Switch
      • Flowchart Symbols
      • Exercise Questions
    • Iterations
      • While Loops
      • For Loop
      • Exercises
    • Java Type Casting
    • Strings
      • Common String Practices
      • String Formatting
      • Java Special Characters
    • Collection
      • Arrays
      • For Each Loop
      • ArrayList
      • Exercise Questions
    • Static Methods
      • (Aside) Clearing your Console
    • Randomness in Java
    • Delayed Output in Java
    • Java Output Formatting
    • Java Style Guide
  • 🛠️JavaScript Programming
    • Our Programming Editor & Workflow
      • Hello, world!
      • Commenting & Variables
      • Data in JavaScript
      • Operators
      • String Formatting
      • Getting User Input
    • JavaScript Exercise Set 1
    • Making Decisions
      • Comparing Values
      • Combining Boolean Comparisons
      • Creating Branches
    • JavaScript Exercise Set 2
    • While Loops
      • Infinite While Loop
      • While Loops and Numbers
      • While Loops and Flags
      • While loops w/ Strings
    • JavaScript Exercise Set 3
    • Subprograms & Functions
      • Creating a Function in JavaScript
      • Function with Input and Assignable Output
    • JavaScript Exercise Set 4
  • 💾Topics in CS
    • Computer Environments & Systems
      • Computer Components
        • In-depth Explanations
      • File Maintenance
      • Computer & Safety
      • Software Development
      • Bits & Binary
    • Careers related to Computer Science
    • Postsecondary Opportunities
Powered by GitBook
On this page
  • Linear/Sequential Search
  • Binary Search
  • Linear vs Binary Search
  • Connected Reading
  1. Python Programming
  2. Competitive Programming
  3. Is This Sum Possible?

Searching for a value

PreviousIs the dataset sorted?NextDetermine if the difference between an integer from the array and the target value exists

Last updated 10 months ago

Linear/Sequential Search

PSEUDOCODE

Let L represent an array of values
    Let n represent the size of the array
Let T represnet target value T, 
Let i represent index of L

1. Set i to 0.
2. If L[i] = T, the search terminates successfully; return i.
3. If i < n, Increase i by 1 and go to step 2. 
4. If i == n, the search terminates unsuccessfully.

is the act of looking through a collection from the start and determining the index of the value you are searching for.

  • Best Case Scenario: The first item is the target value

  • Average Case: The target is somewhere near the middle of the dataset

  • Worst Case: The target is not found, and you have analyzed every single value

By encountering the worst case scenario, we can potentially have a slow algorithm.

If the array had a million data points, and our target value is not one of the given value, the algorithm would be required to make a million comparisons to determine it is not in the array.

The study of efficiency of algorithm is called .

The search algorithm is called "linear" because it individually searches for the target from start to end.

Binary Search

PSEUDOCODE

Let A represent a sorted array of values
    Let n represent the size of A
Let L represent left index point
Let R represent right index point
Let m represent middle index point
Let T represent the target value of interest

1.  L = 0
2.  R = n − 1
3.  while L <= R do:
4.      m := floor((L + R) / 2)
5.      if A[m] < T then
6.          L := m + 1
7.      else if A[m] > T then
8.          R := m − 1
9.      else:
10.         return m
11. return unsuccessful

The midpoint changes every iteration to shrink the search range within the dataset until the target is found or not found.

Linear vs Binary Search

Let A be a list of integers from 1 to 100 inclusively.
Let T be a value of 77

LinearSearch(A, T) would do 77 comparisons to determine that 77 exists at index 76

BinarySearch(A, T) would do the following comparisons:
Comparison 1 -> Is T a value of 50? (No) ... 50 = (1 + 100) / 2 rounded down
Comparison 2 -> Is T > 50? (Yes)
    - At this point our search range was updated to 51 to 100 rather than 1 to 100

Comparison 3 -> Is T a value of 75? (No)
Comparison 4 -> Is T > 75? (Yes)
    - At this point our search range is 76 to 100
    
Comparison 5 -> Is T a value of 88 (No)
Comparison 6 -> Is T > 88 (No)
    - At this point our search range is 76 to 88

Comparison 7 -> Is T a value of 81 (No)
Comparison 8 -> Is T > 81 (No)
    - At this point our search range is 76 to 81

Comparison 9 -> Is T a value of 78 (No)
Comparison 10 -> Is T > 78 (No)
    - At this point our search range is 76 to 78

Comparison 10 -> Is T a value of 77 (Yes)
    - The search is now completed

As the dataset gets bigger, the linear search will do more comparisons compared to binary search. This classifies that binary search is a faster algorithm than linear search.

The weakness of binary search are the following:

  • The dataset must be sorted (which increases complexity if the dataset is not sorted)

  • The dataset must be comparable

  • The algorithm cannot be used to find multiple instances or duplicates; it can only generate a single answer

Connected Reading

is a searching algorithm that works only on sorted and comparable dataset. It is considered to be significantly faster than linear search because it ignores where the target value cannot exist in the dataset by comparing the target with its generated midpoint.

Linear Search ()

Binary Search ()

Big-O Notation ()

🐍
Linear Search
Complexity Analysis
Binary Search
Link
Link
Link