Linear Search Algorithm

Introduction

The linear search algorithm is a foundational method for locating a target element within an array by sequentially checking each element. This algorithm, while simple, proves effective for small datasets.

Algorithm Overview

1. If the array is empty, return -1, indicating the target is not found.
2. Iterate through each element num in the array.
3. If num matches the target, return 1, indicating the element is found.
4. If no match is found after iterating through the entire array, return -1.

TypeScript Implementation

export default function linearSearch(nums: number[], target: number): number {
  for (let i: number = 0; i < nums.length; i++) {
    if (nums[i] === target) return i;
  }
  return -1;
}

const nums: number[] = [2, 41, 4, 1, 7];
const target: number = 3;
linearSearch(nums.slice(), target); // 🔄 Using slice to avoid modifying the original array

Important Note:

Here, I'm using the slice method on the nums array. This lets me work with a copy of the data instead of the original data.

In this code snippet, I'm emphasizing the use of strict types, even though some types are inferred from their initial values. Explicitly defining types, even when inferred, enhances readability, consistency, and documentation within the code.

• Clarity: Assigning explicit types makes code easier to understand.
• Consistency: It ensures uniformity and simplifies future modifications.
• Documentation: Helps clarify variable usage and intentions for better comprehension.

When dealing with real-world data in data structures, algorithms, or any data-related tasks, it's better not to change the original data directly. Instead, it's best practice to create a duplicate or copy of the data and perform modifications on the copied version while keeping the original dataset unchanged.

Complexity Analysis

• Best Case: O(1) - When the target element is found at the beginning of the array.
• Average Case: O(n) - When the target element is present somewhere in the middle of the array.
• Worst Case: O(n) - When the target element is not present in the array or located at the end of the array.

Binary Search Algorithm

Introduction

The binary search algorithm efficiently finds a target element within a sorted array by repeatedly dividing the search interval in half. This makes it particularly effective for large datasets.

Algorithm Overview

1. Initialize two pointers, left and right, representing the start and end of the array.
2. Loop until left is less than or equal to right.
3. Calculate the middle element.
4. If the target matches the middle element, return 1, indicating the element is found.
5. If the target is less than the middle value, continue searching the left portion of the array.
6. If the target is greater than the middle value, continue searching the right portion of the array.
7. If the target is not found, increment left and decrement right.
8. Return -1 if the target is not present in the array.

TypeScript Implementation

export default function binarySearch(nums: number[], target: number): number {
  if (nums.length === 0) return -1;
  let left: number = 0;
  let right: number = nums.length - 1;

  while (left <= right) {
    const mid: number = Math.floor(left + (right - left) / 2);
    if (nums[mid] === target) {
      return mid;
    } else if (nums[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  return -1;
}

const nums: number[] = [1, 2, 3, 4, 5];
const target: number = 0;
binarySearch(nums.slice(), target); // 🔄 Using slice to avoid modifying the original array

Complexity Analysis

• Best Case: O(1) - When the target element is found at the middle of the array.
• Average Case: O(logn) - When the target element is present somewhere in the middle of the array.
• Worst Case: O(logn) - When the target element is not present in the array or located at the end of the array.

Note

The array must be sorted in either ascending or descending order for the binary search to operate efficiently.

Explaining the variance between left + (right - left) / 2 and (left + right) / 2:

1. Both calculate the middle index in binary search.
2. The former prevents potential integer overflow by first computing the difference before division.
3. It's a safer option for handling large values or scenarios near integer limits to avoid arithmetic overflow.

Let's consider a scenario where the input array is sorted in descending order, but our code is optimized for arrays sorted in ascending order. To handle both scenarios effectively, we'll need to make adjustments to our code.

export default function binarySearch(nums: number[], target: number): number {
  if (nums.length === 0) return -1;

  let left: number = 0;
  let right: number = nums.length - 1;

  const isAscending: boolean = nums[left] < nums[right];

  while (left <= right) {
    const mid: number = Math.floor(left + (right - left) / 2);

    if (nums[mid] === target) {
      return mid;
    }

    if (isAscending) {
      if (nums[mid] < target) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    } else {
      if (nums[mid] > target) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }
  }

  return -1;
}

const nums: number[] = [1, 2, 3, 4, 5];
const target: number = 2;
binarySearch(nums.slice(), target); // 🔄 Using slice to avoid modifying the original array

In this scenario, our existing code is optimized for ascending order, but by introducing a check for the order of the input array (isAscending), we've made it adaptable to handle both ascending and descending order scenarios efficiently.

You can find all the code samples here

Conclusion

Understanding these search algorithms is crucial for developers when choosing the right approach for different scenarios. The linear search, though simple, is effective for smaller datasets, while the binary search excels in efficiently handling larger, sorted arrays. Depending on your specific use case, you can leverage these algorithms to optimize your code.

Thank you for reading this far; your support means a lot! If you have any questions, please don't hesitate to ask in the comments. Don't forget to like and share the article – your appreciation is highly valued. Your feedback and suggestions are also more than welcome. 🙏👍😊