Programming Languages war
Python, PHP, Javascript (Nodejs)
Linear and binary search

Programming Languages war Python, PHP, Javascript (Nodejs) Linear and binary search

Carlos Rivas's photo
Carlos Rivas

Published on May 17, 2021

6 min read

Hey my friends, a new post about this war. I don't know which is better, but I'll try to figure it out. I hope y'all enjoy this series. Here we go!

In this post, I'm going to write about linear and binary search.

According to Wikipedia 😜.

Linear Search: In computer science, a linear search or sequential search is a method for finding an element within a list. It sequentially checks each element of the list until a match is found or the whole list has been searched.

Binary Search: In computer science, binary search, also known as half-interval search,[1] logarithmic search,[2] or binary chop,[3] is a search algorithm that finds the position of a target value within a sorted array.[4][5] Binary search compares the target value to the middle element of the array. If they are not equal, the half in which the target cannot lie is eliminated and the search continues on the remaining half, again taking the middle element to compare to the target value, and repeating this until the target value is found. If the search ends with the remaining half being empty, the target is not in the array.

We need to know that Binary Search need and array sorted.

I'm going to explain in each language, so, here we go!

Python

I created a class with two methods.

The first method 'linear', It's simple, I just have to check position by position until I get the value in the dictionary.

The second method 'binary', The searching starts in middle of the dictionary, and I have to reduce the space of searching each time.

# Define the class search 

class Search:

  # Define the method linear.
  def linear(self, arr, value):
    # Loop with the method for.
    for index, x in enumerate(arr):
      # Validate if the value and the value of this position are the same.
      if x == value:
        # Return position.
        return index
    # Return if the value doesn't exist in the dictionary.
    return -1

  # Define the method binary
  def binary(self, arr, start, end, value):
    # Validate if the end is gather than the start
    if end >= start:

        # Get the middle knowing the end and start
        # Doble "/" means to get the floor of the result of division.
        mid = start + (end - start) // 2

        # Validate if the value and the value of this position are equal.
        if arr[mid] == value:
            # Return position
            return mid

        # Validate if the value of this position is greater than value.
        elif arr[mid] > value:
            # Set the new end position
            return self.binary(arr, start, mid-1, value)

        else:
            # Set the new start position
            return self.binary(arr, mid + 1, end, value)

    # Return if the value doesn't exist in dictionary.
    else:
        return -1

# Dictionary
arr = [10, 20, 30, 50, 60, 80, 100, 110, 130, 170]
# The value to search.
value = 110
# Instance class
sol = Search()
# Call the method
result = sol.linear(arr, value)
# Print result
print(result)
# Call the method
result = sol.binary(arr, 0, len(arr)-1,value)
# Print result
print(result)

PHP

I created a class with two methods.

The first method 'linear', It's simple, I just have to check position by position until I get the value in the array.

The second method 'binary', The searching starts in middle of the array, and I have to reduce the space of searching each time.

<?php
// Define the class search. 
class Search {

  // Define the method linear.
  function linear($arr, $value) {
    // Loop with the method for.
    for ($index = 0; $index < count($arr); $index++) {
      // Validate if the value and the value of this position are the same.
      if ($arr[$index] == $value) {
        // Return position.
        return $index;
      }
    }
    // Return if the value doesn't exist in the array.
    return -1;
  }

  // Define the method binary.
  function binary($arr, $start, $end, $value) {
    // Validate if the end is gather than the start.
    if ($end >= $start) {

      // Get the middle knowing the end and start.
      // The method "floor" means to get the floor of the result.
      $mid = floor($start + ($end - $start) / 2);

      // Validate if the value and the value of this position are the same.
      if ($arr[$mid] == $value) {
        // Return position.
        return $mid;

      // Validate if the value of this position is greater than value.
      } else if ($arr[$mid] > $value) {
        // Set the new end position.
        return $this->binary($arr, $start, $mid - 1, $value);
      } else {
        // Set the new start position.
        return $this->binary($arr, $mid + 1, $end, $value);
      }

    // Return if the value doesn't exist in the array.
    } else {
      return -1;
    }
  }
}

// Array.
$arr = [10, 20, 30, 50, 60, 80, 100, 110, 130, 170];
// The value to search.
$value = 110;
// Instance class.
$sol = new Search();
// Call the method.
$result = $sol->linear($arr, $value);
// Print result.
var_dump($result);
// Call the method.
$result = $sol->binary($arr, 0, count($arr) - 1, $value);
// Print result.
var_dump($result);
?>

Javascript

I created a class with two methods.

The first method 'linear', It's simple, I just have to check position by position until I get the value in the array.

The second method 'binary', The searching starts in middle of the array, and I have to reduce the space of searching each time.

// Define the class search.
class Search {

  // Define the method linear.
  linear(arr, value) {
    // Loop with the method for.
    for (let index = 0; index < arr.length; index++) {
      // Validate if the value and the value of this position are the same.
      if (arr[index] == value) {
        // Return position.
        return index;
      }
    }
    // Return if the value doesn't exist in the array.
    return -1;
  }

  // Define the method binary.
  binary(arr, start, end, value) {

    // Validate if the end is gather than the start.
    if (end >= start) {

      // Get the middle knowing the end and start.
      // the method "Math.floor" means to get the floor of the result.
      const mid = Math.floor(start + (end - start) / 2);

      // Validate if the value and the value of this position are the same.
      if (arr[mid] == value) {
        // Return position.
        return mid;

      // Validate if the value of this position is greater than value.
      } else if (arr[mid] > value) {
        // Set the new end position.
        return this.binary(arr, start, mid - 1, value);
      } else {
        // Set the new start position.
        return this.binary(arr, mid + 1, end, value);
      }

    // Return if the value doesn't exist in the array.
    } else {
      return -1;
    }
  }
}

// Array.
const arr = [10, 20, 30, 50, 60, 80, 100, 110, 130, 170];
// The value to search.
const value = 110;
// Instance class.
const sol = new Search();
// Call the method.
let result = sol.linear(arr, value);
// Print result.
console.log(result);
// Call the method.
result = sol.binary(arr, 0, arr.length - 1, value);
// Print result.
console.log(result);

Conclusion

  • Structure: Each language has a little difference.
  • Lines: Python: 33, PHP: 37, Javascript: 34
  • Time to execution: Python: 97 ms, PHP: 77 ms, Javascript: 122 ms

Would you like that I write more search methods?

I hope you enjoy my post and remember that I am just a Dev like you!

Β 
Share this