Binary Search With Alo

November 23, 2023
0

Binary Search With Alo


Scenario: Cooking Perfect Pasta 

Imagine you're cooking pasta, and you want to find the optimal cooking time to achieve that ideal "al dente" texture. You know the cooking time falls within a certain range, say between 1 and 20 minutes. To find the perfect time, you decide to use binary search. Consider Target Time is 15 min.

Consider the same with your lucky number finding from sorted list of numbers.



Quick Example

Can You Guess How Quickly This Binary Search Finds '42' in a List of 100 Numbers? in Just 7 steps

Step

Range

Middle Number

Decision

1

1 to 100

50

42 < 50, go left

2

1 to 49

25

42 > 25, go right

3

26 to 49

37

42 > 37, go right

4

38 to 49

43

42 < 43, go left

5

38 to 42

40

42 > 40, go right

6

41 to 42

41

42 > 41, go right

7

42 to 42

42

42 found!

Introducing Alo

If you're all about giving instructions and getting things done, you might just have a friend in your life like Alo.


🚀 Meet Alo: The MIND-BLOWING Instruction-Based
Genius! No Senses, No Thoughts, But Can Master Algorithmic Concepts? 🤯
He not only teaches you but also provides challenges to make your day happier.😃


Alo's Quest:

Discover Your Lucky Number in Just 4 Steps or Less!

List of Numbers1, 3, 5, 7, 9, 11, 13, 15, 22

7 is Your lucky number? or you can enter your lucky number.


Alo will find it by your instructions.


Challenges and Solutions


1. How to Save All Numbers into a List


What kinds of numbers are they? 


Alo may not have thoughts, Where he will store all numberes ?


Check out how Alo can save all numbers.

C#
Checkout Code
Java
Checkout Code
JavaScript
Checkout Code
Python
Checkout Code
Rust
Checkout Code 
// Create an array of sorted numbers to search within
int[] sortedNumbers = { 1, 3, 5, 7, 9, 11, 13, 15, 22 };
        
    
// Create an array of sorted numbers to search within
int[] sortedNumbers = { 1, 3, 5, 7, 9, 11, 13, 15, 22 };
        
    
// Create an array of sorted numbers to search within
const sortedNumbers = [1, 3, 5, 7, 9, 11, 13, 15, 22];

# Create an array of sorted numbers to search within
sortedNumbers = [1, 3, 5, 7, 9, 11, 13, 15, 22]

// Create an array of sorted numbers to search within
let sorted_numbers = vec![1, 3, 5, 7, 9, 11, 13, 15, 22];


2.Get Your Lucky Number as Input

How Can I Store Your Lucky Number as Input and Remember It While Searching for Your Number?


Now Alo can read your input.

C#
Checkout Code
Java
Checkout Code
JavaScript
Checkout Code
Python
Checkout Code
Rust
Checkout Code 
// Prompt the user to enter their favorite number
 Console.Write("Enter your favorite number: ");
    
// Read the user's input from the console and parse it as an integer
 int luckyNumber = int.Parse(Console.ReadLine());


// Prompt the user to enter their favorite number
System.out.print("Enter your favorite number: ");

// Read the user's input from the console and parse it as an integer
int luckyNumber = Integer.parseInt(System.console().readLine()); 


// Prompt the user to enter their favorite number
let lucky_number_str = prompt("Enter your favorite number:");

// Read the user's input from the console and parse it as an integer
let luckyNumber = parseInt(favorite_number_str);
# Prompt the user to enter their lucky number
# Read the user's input from the console and parse it as an integer
luckyNumber = int(input("Please enter your lucky Number: "))



// Prompt the user to enter their lucky number
println!("Please enter your lucky Number: ");

let mut input = String::new();
io::stdin()
    .read_line(&mut input)
    .expect("Failed to read line");

// Parse the user's input into the 'lucky_number' variable
let lucky_number: i32 = input.trim().parse().expect("Invalid input");


3. Start with

🔍 Which Direction Does Alo Search?
🚶‍♂️ How Does He Count Steps?
🤔 And How Does He Identify the Number of Items in a List?

Let's see how to tackle and sort out all these tricky questions in your favorite language.

C#
Checkout Code
Java
Checkout Code
JavaScript
Checkout Code
Python
Checkout Code
Rust
Checkout Code 
// Initialize variables to keep track of left side start from 0 
int leftSide = 0;

// Calculate the initial right-side index of the search range.
// The right-side index is set to one less than the length of the 'sortedNumbers' array.
// This is because arrays are start from zero-based, so the last element's index is 'array.Length - 1'.
int rightSide = sortedNumbers.Length - 1;

//Alo start his steps counting from 0 
int Alo_Steps_Count = 0;
    
// Initialize variables to keep track of the left side (starting from 0)
int leftSide = 0;

// Calculate the initial right-side index of the search range.
int rightSide = sortedNumbers.length - 1;

// Alo start his steps counting from 0
int AloStepsCount = 0;

// Initialize variables to keep track of the left side (starting from 0)
let leftSide = 0;

// Calculate the initial right-side index of the search range
let rightSide = sortedNumbers.length - 1;

// Also start his steps counting from 0
let AloStepsCount = 0;
        
 
# Initialize variables to keep track of the left side (starting from 0)
leftSide = 0

# Calculate the initial right-side index of the search range
rightSide = len(sortedNumbers) - 1

# Also start his steps counting from 0
AloStepsCount = 0
        
    
// Initialize variables to keep track of the left side (starting from 0)
let mut left_side = 0;

// Calculate the initial right-side index of the search range
let mut right_side = sorted_numbers.len() - 1;

// Also start his steps counting from 0
let mut alo_steps_count = 0;


4. Cut the list into two parts.

How will Alo 🚶‍♂️ walk until the condition is satisfied? 🛤️🙂
How can Alo increment the steps one by one? 🚶‍♂️➕1️⃣
How to cut a large number list into two parts? 📈✂️

Assess Alo's walking style based on conditions and their cutting skills in each step.

C#
Checkout Code
Java
Checkout Code
JavaScript
Checkout Code
Python
Checkout Code
Rust
Checkout Code 
// Alo is walking on the condition: 'leftSide less than or equal to rightSide'.
// Once the condition is met, he will exit the walking mode.
while (leftSide <= rightSide)
{
    // Increment the step count for each iteration
    AloStepsCount++;

    // Calculate the middle index of the current search range
    int middle = leftSide + (rightSide - leftSide) / 2;

}

// Alo is walking on the condition: 'leftSide less than or equal to rightSide'.
// Once the condition is met, he will exit the walking mode.
while (leftSide <= rightSide) {
    // Increment the step count for each iteration
    AloStepsCount++;

    // Calculate the middle index of the current search range
    int middle = leftSide + (rightSide - leftSide) / 2;

}

// Alo is walking on the condition: 'leftSide less than or equal to rightSide'.
// Once the condition is met, he will exit the walking mode.
while (leftSide <= rightSide) {
// Increment the step count for each iteration
AloStepsCount++;

// Calculate the middle index of the current search range
const middle = Math.floor((leftSide + rightSide) / 2);
}
 # Alo is walking on the condition: 'leftSide less than or equal to rightSide'.
        # Once the condition is met, he will exit the walking mode.
while leftSide <= rightSide:
    # Increment the step count for each iteration
    AloStepsCount += 1

    # Calculate the middle index of the current search range
    middle = leftSide + (rightSide - leftSide) // 2

    
// Alo is walking on the condition: 'leftSide less than or equal to rightSide'.
// Once the condition is met, he will exit the walking mode.
while left_side <= right_side {
    // Increment the step count for each iteration
        alo_steps_count += 1;

    // Calculate the middle index of the current search range
        let middle = left_side + (right_side - left_side) / 2;
}


5. Is LuckyNumber in the middle?.

How can Alo check if the lucky number is in the middle? 🍀🔍
If the lucky number is present in the middle, then what should happen? 🍀🤔
Which path should he consider, left or right? 🚶‍♂️➡️
If the lucky number is not found after all the searches, what should happen? 🍀❓

Is the lucky number in the middle? 🍀 If not, which way to go? 🚶‍♂️➡️

C#
Checkout Code
Java
Checkout Code
JavaScript
Checkout Code
Python
Checkout Code
Rust
Checkout Code 
// Alo is walking on the condition: 'leftSide less than or equal to rightSide'.
// Once the condition is met, he will exit the walking mode.
while (leftSide <= rightSide)
{
    // Increment the step count for each iteration
    AloStepsCount++;

    // Calculate the middle index of the current search range
    int middle = leftSide + (rightSide - leftSide) / 2;

    // Check if the 'luckyNumber' is found at the middle index
    if (sortedNumbers[middle] == luckyNumber)
    {
        // Print a success message when the 'luckyNumber' is found, along with the number of steps taken
        Console.WriteLine("🎉 Alo found Element at index {0}. He took {1} steps to find it.", middle, AloStepsCount);
        return; // Exit the program
    }

    // Adjust the search range based on the value of the 'luckyNumber'
    if (sortedNumbers[middle] < luckyNumber)
        leftSide = middle + 1; // Search the right side of the array
    else
        rightSide = middle - 1; // Search the left side of the array
}
// If the 'luckyNumber' is not found, print a message indicating it and the number of steps taken
Console.WriteLine("😞 Alo not found Element in the Array. He took {0} steps.", AloStepsCount);

// Alo is walking on the condition: 'leftSide less than or equal to rightSide'.
// Once the condition is met, he will exit the walking mode.
while (leftSide <= rightSide) {
    // Increment the step count for each iteration
    AloStepsCount++;

    // Calculate the middle index of the current search range
    int middle = leftSide + (rightSide - leftSide) / 2;

    // Check if the 'luckyNumber' is found at the middle index
    if (sortedNumbers[middle] == luckyNumber) {
        // Print a success message when the 'luckyNumber' is found, along with the number of steps taken
        System.out.printf("🎉 Alo found Element at index %d. He took %d steps to find it.%n", middle, AloStepsCount);
        return; // Exit the program
    }

    // Adjust the search range based on the value of the 'luckyNumber'
    if (sortedNumbers[middle] < luckyNumber)
        leftSide = middle + 1; // Search the right side of the array
    else
        rightSide = middle - 1; // Search the left side of the array
}

// If the 'luckyNumber' is not found, print a message indicating it and the number of steps taken
System.out.printf("😞 Alo not found Element in the Array. He took %d steps.%n", AloStepsCount);


// Alo is walking on the condition: 'leftSide less than or equal to rightSide'.
// Once the condition is met, he will exit the walking mode.
while (leftSide <= rightSide) {
    // Increment the step count for each iteration
    AloStepsCount++;

    // Calculate the middle index of the current search range
    const middle = Math.floor((leftSide + rightSide) / 2);

    // Check if the 'luckyNumber' is found at the middle index
    if (sortedNumbers[middle] === luckyNumber) {
    // Print a success message when the 'luckyNumber' is found, along with the number of steps taken
      console.log(`🎉 Alo found Element at index ${middle}. He took ${AloStepsCount} steps to find it.`);
      break; // Exit the loop
    }

    // Adjust the search range based on the value of the 'luckyNumber'
    if (sortedNumbers[middle] < luckyNumber)
      leftSide = middle + 1; // Search the right side of the array
    else
      rightSide = middle - 1; // Search the left side of the array
}

// If the 'luckyNumber' is not found, print a message indicating it and the number of steps taken
if (leftSide > rightSide) {
console.log(`😞 Alo not found Element in the Array. He took ${AloStepsCount} steps.`);
}
 # Alo is walking on the condition: 'leftSide less than or equal to rightSide'.
        # Once the condition is met, he will exit the walking mode.
while leftSide <= rightSide:
# Increment the step count for each iteration
AloStepsCount += 1

# Calculate the middle index of the current search range
middle = leftSide + (rightSide - leftSide) // 2

# Check if the 'luckyNumber' is found at the middle index
if sortedNumbers[middle] == luckyNumber:
    # Print a success message when the 'luckyNumber' is found, along with the number of steps taken
    print(f"🎉 Alo found Element at index {middle}. He took {AloStepsCount} steps to find it.")
    break

    # Adjust the search range based on the value of the 'luckyNumber'
if sortedNumbers[middle] < luckyNumber:
    leftSide = middle + 1  # Search the right side of the array
else:
    rightSide = middle - 1  # Search the left side of the array

    # If the 'luckyNumber' is not found, print a message indicating it and the number of steps taken
if leftSide > rightSide:
print(f"😞 Alo not found Element in the Array. He took {AloStepsCount} steps.")

    
// Alo is walking on the condition: 'leftSide less than or equal to rightSide'.
// Once the condition is met, he will exit the walking mode.
while left_side <= right_side {
    // Increment the step count for each iteration
    alo_steps_count += 1;

    // Calculate the middle index of the current search range
    let middle = left_side + (right_side - left_side) / 2;

    // Check if the 'lucky_number' is found at the middle index
    if sorted_numbers[middle] == lucky_number {
        // Print a success message when the 'lucky_number' is found, along with the number of steps taken
        println!(
            "🎉 Alo found Element at index {}. He took {} steps to find it.",
            middle, alo_steps_count
        );
        return;
    }

    // Adjust the search range based on the value of the 'lucky_number'
    if sorted_numbers[middle] < lucky_number {
        left_side = middle + 1; // Search the right side of the array
    } else {
        right_side = middle - 1; // Search the left side of the array
    }
}

// If the 'lucky_number' is not found, print a message indicating it and the number of steps taken
println!(
    "😞 Alo not found Element in the Array. He took {} steps.",
    alo_steps_count
);


Dry Run

Lets check Alo's code with dry run

A dry run is a valuable practice to ensure that the program works as expected before executing it on a computer.

Left Index

Right Index

Middle Index

Middle Element

Lucky Number

Step

Comment

0

8

4

9

7

1

Initial state

0

3

1

3

7

2

Lucky number > Middle

2

3

2

5

7

3

Lucky number > Middle

3

3

3

7

7

4

Lucky number == Middle

 

 

 

 

 

 

Element found!



5. Now, you can write the program in your favorite language.

Combine all the steps into a single program.

C#
Checkout Code
Java
Checkout Code
JavaScript
Checkout Code
Python
Checkout Code
Rust
Checkout Code 
        
using System;

class Program
{
    public static void Main()
    {
        // Create an array of sorted numbers to search within
        int[] sortedNumbers = { 1, 3, 5, 7, 9, 11, 13, 15, 22 };

        // Prompt the user to enter their lucky number
        Console.Write("Please enter your lucky Number: ");

        // Read and parse the user's input into the 'luckyNumber' variable
        int luckyNumber = int.Parse(Console.ReadLine());

        // Initialize variables to keep track of the left side (starting from 0)
        int leftSide = 0;

        // Calculate the initial right-side index of the search range
        int rightSide = sortedNumbers.Length - 1;

        // Also start his steps counting from 0
        int AloStepsCount = 0;

        // Start a binary search loop
        while (leftSide <= rightSide)
        {
            // Increment the step count for each iteration
            AloStepsCount++;

            // Calculate the middle index of the current search range
            int middle = leftSide + (rightSide - leftSide) / 2;

            // Check if the 'luckyNumber' is found at the middle index
            if (sortedNumbers[middle] == luckyNumber)
            {
                // Print a success message when the 'luckyNumber' is found, along with the number of steps taken
                Console.WriteLine("🎉 Alo found Element at index {0}. He took {1} steps to find it.", middle, AloStepsCount);
                return; // Exit the program
            }

            // Adjust the search range based on the value of the 'luckyNumber'
            if (sortedNumbers[middle] < luckyNumber)
                leftSide = middle + 1; // Search the right side of the array
            else
                rightSide = middle - 1; // Search the left side of the array
        }

        // If the 'luckyNumber' is not found, print a message indicating it and the number of steps taken
        Console.WriteLine("😞 Alo not found Element in the Array. He took {0} steps.", AloStepsCount);
    }
}

    
        
import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        // Create an array of sorted numbers to search within
        int[] sortedNumbers = { 1, 3, 5, 7, 9, 11, 13, 15, 22 };

        // Prompt the user to enter their lucky number
        System.out.print("Please enter your lucky Number: ");

        // Read and parse the user's input into the 'luckyNumber' variable
        int luckyNumber = Integer.parseInt(System.console().readLine());

        // Initialize variables to keep track of the left side (starting from 0)
        int leftSide = 0;

        // Calculate the initial right-side index of the search range.
        int rightSide = sortedNumbers.length - 1;

        // Also start his steps counting from 0
        int AloStepsCount = 0;

        // Start a binary search loop
        while (leftSide <= rightSide) {
            // Increment the step count for each iteration
            AloStepsCount++;

            // Calculate the middle index of the current search range
            int middle = leftSide + (rightSide - leftSide) / 2;

            // Check if the 'luckyNumber' is found at the middle index
            if (sortedNumbers[middle] == luckyNumber) {
                // Print a success message when the 'luckyNumber' is found, along with the number of steps taken
                System.out.printf("🎉 Alo found Element at index %d. He took %d steps to find it.%n", middle, AloStepsCount);
                return; // Exit the program
            }

            // Adjust the search range based on the value of the 'luckyNumber'
            if (sortedNumbers[middle] < luckyNumber)
                leftSide = middle + 1; // Search the right side of the array
            else
                rightSide = middle - 1; // Search the left side of the array
        }

        // If the 'luckyNumber' is not found, print a message indicating it and the number of steps taken
        System.out.printf("😞 Alo not found Element in the Array. He took %d steps.%n", AloStepsCount);
    }
}

        

    

const sortedNumbers = [1, 3, 5, 7, 9, 11, 13, 15, 22];
const readline = require('readline');

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout
});

rl.question('Enter your favorite number: ', (luckyNumber) => {
  luckyNumber = parseInt(luckyNumber);

  // Initialize variables to keep track of the left side (starting from 0)
  let leftSide = 0;

  // Calculate the initial right-side index of the search range
  let rightSide = sortedNumbers.length - 1;

  // Also start his steps counting from 0
  let AloStepsCount = 0;

  // Start a binary search loop
  while (leftSide <= rightSide) {
    // Increment the step count for each iteration
    AloStepsCount++;

    // Calculate the middle index of the current search range
    const middle = Math.floor((leftSide + rightSide) / 2);

    // Check if the 'luckyNumber' is found at the middle index
    if (sortedNumbers[middle] === luckyNumber) {
      // Print a success message when the 'luckyNumber' is found, along with the number of steps taken
      console.log(`🎉 Alo found Element at index ${middle}. He took ${AloStepsCount} steps to find it.`);
      break; // Exit the loop
    }

    // Adjust the search range based on the value of the 'luckyNumber'
    if (sortedNumbers[middle] < luckyNumber)
      leftSide = middle + 1; // Search the right side of the array
    else
      rightSide = middle - 1; // Search the left side of the array
  }

  // If the 'luckyNumber' is not found, print a message indicating it and the number of steps taken
  if (leftSide > rightSide) {
    console.log(`😞 Alo not found Element in the Array. He took ${AloStepsCount} steps.`);
  }

  rl.close();
});
    
    
    
        
# Create an array of sorted numbers to search within
sortedNumbers = [1, 3, 5, 7, 9, 11, 13, 15, 22]

# Prompt the user to enter their lucky number
luckyNumber = int(input("Please enter your lucky Number: "))

# Initialize variables to keep track of the left side (starting from 0)
leftSide = 0

# Calculate the initial right-side index of the search range
rightSide = len(sortedNumbers) - 1

# Also start his steps counting from 0
AloStepsCount = 0

# Start a binary search loop
while leftSide <= rightSide:
    # Increment the step count for each iteration
    AloStepsCount += 1

    # Calculate the middle index of the current search range
    middle = leftSide + (rightSide - leftSide) // 2

    # Check if the 'luckyNumber' is found at the middle index
    if sortedNumbers[middle] == luckyNumber:
        # Print a success message when the 'luckyNumber' is found, along with the number of steps taken
        print(f"🎉 Alo found Element at index {middle}. He took {AloStepsCount} steps to find it.")
        break

    # Adjust the search range based on the value of the 'luckyNumber'
    if sortedNumbers[middle] < luckyNumber:
        leftSide = middle + 1  # Search the right side of the array
    else:
        rightSide = middle - 1  # Search the left side of the array

# If the 'luckyNumber' is not found, print a message indicating it and the number of steps taken
if leftSide > rightSide:
    print(f"😞 Alo not found Element in the Array. He took {AloStepsCount} steps.")

        
    
        
use std::io;

fn main() {
    // Create an array of sorted numbers to search within
    let sorted_numbers = vec![1, 3, 5, 7, 9, 11, 13, 15, 22];

    // Prompt the user to enter their lucky number
    println!("Please enter your lucky Number: ");

    let mut input = String::new();
    io::stdin()
        .read_line(&mut input)
        .expect("Failed to read line");

    // Parse the user's input into the 'lucky_number' variable
    let lucky_number: i32 = input.trim().parse().expect("Invalid input");

    // Initialize variables to keep track of the left side (starting from 0)
    let mut left_side = 0;

    // Calculate the initial right-side index of the search range
    let mut right_side = sorted_numbers.len() - 1;

    // Also start his steps counting from 0
    let mut alo_steps_count = 0;

    // Start a binary search loop
    while left_side <= right_side {
        // Increment the step count for each iteration
        alo_steps_count += 1;

        // Calculate the middle index of the current search range
        let middle = left_side + (right_side - left_side) / 2;

        // Check if the 'lucky_number' is found at the middle index
        if sorted_numbers[middle] == lucky_number {
            // Print a success message when the 'lucky_number' is found, along with the number of steps taken
            println!(
                "🎉 Alo found Element at index {}. He took {} steps to find it.",
                middle, alo_steps_count
            );
            return;
        }

        // Adjust the search range based on the value of the 'lucky_number'
        if sorted_numbers[middle] < lucky_number {
            left_side = middle + 1; // Search the right side of the array
        } else {
            right_side = middle - 1; // Search the left side of the array
        }
    }

    // If the 'lucky_number' is not found, print a message indicating it and the number of steps taken
    println!(
        "😞 Alo not found Element in the Array. He took {} steps.",
        alo_steps_count
    );
}


Test Cases


Now We Will Test Alo's Programs by Test Cases

The significance of test cases lies in their capacity to identify defects, offering a safety net for developers. Through comprehensive testing of the binary search, developers can uncover errors, inefficiencies, and edge cases, thereby enhancing the algorithm's robustness and reliability.

This thorough testing ensures the reliability of binary search and sets the standard for quality in complex algorithms and applications.

C#
Checkout Code
Java
Checkout Code
JavaScript
Checkout Code
Python
Checkout Code
Rust
Checkout Code 

using Microsoft.VisualStudio.TestTools.UnitTesting;

[TestClass]
public class BinarySearchTests
{
    [TestMethod]
    public void TestBinarySearch_Success()
    {
        // Arrange
        int[] sortedNumbers = { 1, 3, 5, 7, 9, 11, 13, 15, 22 };
        int luckyNumber = 7;

        // Act
        string result = BinarySearchProgram.SearchForLuckyNumber(sortedNumbers, luckyNumber);

        // Assert
        Assert.AreEqual("🎉 Alo found Element at index 3. He took 3 steps to find it.", result);
    }

    [TestMethod]
    public void TestBinarySearch_Failure()
    {
        // Arrange
        int[] sortedNumbers = { 1, 3, 5, 7, 9, 11, 13, 15, 22 };
        int luckyNumber = 10;

        // Act
        string result = BinarySearchProgram.SearchForLuckyNumber(sortedNumbers, luckyNumber);

        // Assert
        Assert.AreEqual("😞 Alo not found Element in the Array. He took 4 steps.", result);
    }
}
        
        
        
        

import org.junit.Test;
import static org.junit.Assert.*;

public class BinarySearchTest {

    @Test
    public void testBinarySearchSuccess() {
        int[] sortedNumbers = { 1, 3, 5, 7, 9, 11, 13, 15, 22 };
        int luckyNumber = 11;

        String result = BinarySearch.searchForLuckyNumber(sortedNumbers, luckyNumber);

        assertEquals("🎉 Alo found Element at index 5. He took 3 steps to find it.", result);
    }

    @Test
    public void testBinarySearchFailure() {
        int[] sortedNumbers = { 1, 3, 5, 7, 9, 11, 13, 15, 22 };
        int luckyNumber = 8;

        String result = BinarySearch.searchForLuckyNumber(sortedNumbers, luckyNumber);

        assertEquals("😞 Alo not found Element in the Array. He took 4 steps.", result);
    }
}
        
        
    
    

const binarySearch = require('./binarySearch'); // Create a separate binary search module

const sortedNumbers = [1, 3, 5, 7, 9, 11, 13, 15, 22];

describe('Binary Search', () => {
  it('should find the lucky number', () => {
    const luckyNumber = 11;
    const result = binarySearch(sortedNumbers, luckyNumber);
    const expected = '🎉 Alo found Element at index 5. He took 3 steps to find it.';
    assert.equal(result, expected);
  });

  it('should not find the lucky number', () => {
    const luckyNumber = 8;
    const result = binarySearch(sortedNumbers, luckyNumber);
    const expected = '😞 Alo not found Element in the Array. He took 4 steps.';
    assert.equal(result, expected);
  });
});


function binarySearch(sortedNumbers, luckyNumber) {
    let leftSide = 0;
    let rightSide = sortedNumbers.length - 1;
    let AloStepsCount = 0;
    
    while (leftSide <= rightSide) {
        AloStepsCount++;
        const middle = Math.floor((leftSide + rightSide) / 2);
    
        if (sortedNumbers[middle] === luckyNumber) {
        return `🎉 Alo found Element at index ${middle}. He took ${AloStepsCount} steps to find it.`;
        }
    
        if (sortedNumbers[middle] < luckyNumber)
        leftSide = middle + 1;
        else
        rightSide = middle - 1;
    }
    
    return `😞 Alo not found Element in the Array. He took ${AloStepsCount} steps.`;
    }
    
    module.exports = binarySearch;
          
        
    
    

import unittest

def binary_search(sorted_numbers, lucky_number):
    left_side = 0
    right_side = len(sorted_numbers) - 1
    alo_steps_count = 0

    while left_side <= right_side:
        alo_steps_count += 1
        middle = left_side + (right_side - left_side) // 2

        if sorted_numbers[middle] == lucky_number:
            return f"🎉 Alo found Element at index {middle}. He took {alo_steps_count} steps to find it."

        if sorted_numbers[middle] < lucky_number:
            left_side = middle + 1  # Search the right side of the array
        else:
            right_side = middle - 1  # Search the left side of the array

    return f"😞 Alo not found Element in the Array. He took {alo_steps_count} steps."

class TestBinarySearch(unittest.TestCase):
    def test_binary_search_success(self):
        sorted_numbers = [1, 3, 5, 7, 9, 11, 13, 15, 22]
        lucky_number = 11
        result = binary_search(sorted_numbers, lucky_number)
        expected = "🎉 Alo found Element at index 5. He took 3 steps to find it."
        self.assertEqual(result, expected)

    def test_binary_search_failure(self):
        sorted_numbers = [1, 3, 5, 7, 9, 11, 13, 15, 22]
        lucky_number = 8
        result = binary_search(sorted_numbers, lucky_number)
        expected = "😞 Alo not found Element in the Array. He took 4 steps."
        self.assertEqual(result, expected)

if __name__ == '__main__':
    unittest.main()
        
        
    
    

fn binary_search(sorted_numbers: &Vec<i32>, lucky_number: i32) -> String {
    let mut left_side = 0;
    let mut right_side = sorted_numbers.len() - 1;
    let mut alo_steps_count = 0;

    while left_side <= right_side {
        alo_steps_count += 1;
        let middle = left_side + (right_side - left_side) / 2;

        if sorted_numbers[middle] == lucky_number {
            return format!(
                "🎉 Alo found Element at index {}. He took {} steps to find it.",
                middle, alo_steps_count
            );
        }

        if sorted_numbers[middle] < lucky_number {
            left_side = middle + 1;
        } else {
            right_side = middle - 1;
        }
    }

    format!("😞 Alo not found Element in the Array. He took {} steps.", alo_steps_count)
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_binary_search_success() {
        let sorted_numbers = vec![1, 3, 5, 7, 9, 11, 13, 15, 22];
        let lucky_number = 11;
        let result = binary_search(&sorted_numbers, lucky_number);
        let expected = "🎉 Alo found Element at index 5. He took 3 steps to find it.";
        assert_eq!(result, expected);
    }

    #[test]
    fn test_binary_search_failure() {
        let sorted_numbers = vec![1, 3, 5, 7, 9, 11, 13, 15, 22];
        let lucky_number = 8;
        let result = binary_search(&sorted_numbers, lucky_number);
        let expected = "😞 Alo not found Element in the Array. He took 4 steps.";
        assert_eq!(result, expected);
    }
}

fn main() {
    // Create an array of sorted numbers to search within
    let sorted_numbers = vec![1, 3, 5, 7, 9, 11, 13, 15, 22];

    // Prompt the user to enter their lucky number
    println!("Please enter your lucky Number: ");

    let mut input = String::new();
    io::stdin()
        .read_line(&mut input)
        .expect("Failed to read line");

    // Parse the user's input into the 'lucky_number' variable
    let lucky_number: i32 = input.trim().parse().expect("Invalid input");

    let result = binary_search(&sorted_numbers, lucky_number);
    println!("{}", result);
}


Run BinarySearch Code on Replit with Your Favorite Language

Create similar example from you imagination and try on Replit online compiler .If you're looking to implement a binary search algorithm and want to try it out in your preferred programming language, you're in luck! You can easily run the above code on the online platform Replit.

1. Binary Search C#

2. Binary Search Java

3. Binary Search Javascript

4. Binary Search Python

5. Binary Search Rust


LeetCode Problems on Binary Search


LeetCode Problem: Binary Search

Description: Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.

You must write an algorithm with O(log n) runtime complexity.

 Example 1:

Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4

Link: Binary Search


LeetCode Problem: First Bad Version

Description: You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.

Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad.

You are given an API bool isBadVersion(version) which returns whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

Example 1:

Input: n = 5, bad = 4
Output: 4
Explanation:
call isBadVersion(3) -> false
call isBadVersion(5) -> true
call isBadVersion(4) -> true
Then 4 is the first bad version.

Link: First Bad Version


LeetCode Problem: Find First and Last Position of Element in Sorted Array

Description: Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.

If target is not found in the array, return [-1, -1].

You must write an algorithm with O(log n) runtime complexity. 

Example 1:

Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]

Link: Find First and Last Position of Element in Sorted Array


Frequently Asked Questions

What is binary search?

Binary search is a searching algorithm used to efficiently locate a specific element within a sorted array. It works by repeatedly dividing the search interval in half, eliminating half of the elements at each step. This results in a time complexity of O(log n), where n is the number of elements.

When should I use binary search?

Binary search is most effective when dealing with large datasets that are already sorted. It is a preferred choice for scenarios where quick retrieval of data is essential. However, it is not suitable for unsorted arrays or dynamic data.

What are the advantages of binary search?

  • Efficiency: Binary search has a time complexity of O(log n), making it significantly faster than linear search for large datasets.
  • Optimal for sorted data: It is ideal for finding elements in sorted arrays, making it a go-to choice for databases and data structures.
  • Precision: Binary search provides accurate results, indicating the presence or absence of an element.

What are the disadvantages of binary search?

  • Requirement of sorted data: Binary search only works on sorted data, which can be a limitation in some applications.
  • Complexity: Implementing binary search correctly can be more challenging than linear search.


Conclusion

Binary search is a highly efficient searching algorithm, particularly suited for large datasets, as it operates with logarithmic time complexity. In contrast to linear search, it excels in terms of speed and resource utilization. This article provides a comprehensive guide to implementing binary search, featuring practical code examples in various programming languages and highlighting its relevance in problem-solving on platforms like LeetCode. In summary, binary search stands as a foundational algorithm that underpins more advanced search methodologies.


Tags:

You may like these posts

Show more

Post a Comment

0Comments

Post a Comment (0)
Share to other apps
Copy Post Link