R Program to Search an Element in a Vector using Binary Search

1. Introduction

Binary Search is an efficient algorithm for finding a specific value from a sorted sequence. By repeatedly dividing the portion of the sequence that could contain the item in half until you've narrowed the possibilities to a single element, binary search minimizes the number of operations compared to other search methods like linear search. In this guide, we'll explore how to implement the Binary Search algorithm in R.

2. Program Overview

The program will:

1. Define a function for the Binary Search algorithm.

2. Create a sorted vector.

3. Use the Binary Search function to find a specific element in the vector.

4. Display whether the element was found and its position if it exists.

3. Code Program

# Define the Binary Search function
binarySearch <- function(vec, x) {
  left <- 1
  right <- length(vec)

  while (left <= right) {
    mid <- floor((left + right) / 2)

    # If element is present at mid
    if (vec[mid] == x) {
      return(mid)
    }

    # If element is greater, ignore left half
    if (vec[mid] < x) {
      left <- mid + 1
    } else {
      # If element is smaller, ignore right half
      right <- mid - 1
    }
  }

  # If we reach here, the element was not present
  return(-1)
}

# Create a sorted vector
numbers <- c(12, 23, 34, 45, 56, 67, 78, 89, 100)

# Search for a specific element using Binary Search
element_to_search <- 67
position <- binarySearch(numbers, element_to_search)

# Display the results
if (position != -1) {
  cat("Element", element_to_search, "found at position:", position, "\n")
} else {
  cat("Element", element_to_search, "not found in the vector.\n")
}

Output:

Element 67 found at position: 6

4. Step By Step Explanation

1. We begin by defining the binarySearch function. This function takes a sorted vector and a value (x) to search for.

2. The left pointer is initialized to the beginning of the vector, and the right pointer to the end.

3. While the left pointer is less than or equal to the right pointer, we calculate the midpoint.

4. If the element at the midpoint is the one we're looking for, we return the position (mid).

5. If the element at the midpoint is less than x, it implies the element (if it exists) must be in the right half. So, we adjust the left pointer to be mid + 1.

6. If the element at the midpoint is greater than x, it suggests the element is in the left half. We then adjust the right pointer to be mid - 1.

7. This process continues until either the element is found or the left pointer exceeds the right pointer.

8. If the element isn't found, we return -1.

9. We then create a sorted vector "numbers" and search for a specific element using the binarySearch function.

10. Depending on the returned position, we display the results accordingly.

Note: It's essential to remember that binary search only works on sorted vectors. If applied to an unsorted vector, the results can be unpredictable.