R Program to implement binary search in array

What is a binary search algorithm?

The binary search algorithm is also called the "half interval algorithm" or "logarithmic algorithm". It can be used to search from a large list of elements. It works faster on large lists than the smaller ones as in sequential search.

The algorithm finds the middle element and compares it with the search item, if not then divides the array into two. A left subarray, an array containing elements before the middle element, and a right subarray which has elements next to the middle element. Now any of these subarrays will be chosen to continue the search according to the possibility of the search element being present. This process will continue until the result or the size of the sublist reduces to zero. It is thus using a divide and conquers method for searching an element in an array. The worst-case time complexity of Binary search is O(logn).

A binary search algorithm searches the element in a sorted array. If the given array is not sorted, the elements need to be sorted first before the search.

How to implement binary search in R?

• A `function` could be written to implement binary search in R. The sorted array and search item can be passed as input variables to the `function`. and,
• Using a `while loop` the middle element is computed first then checks the middle element with the search item if they are matched `return` index of middle element,
• Now rebound the list to check by comparing their values, if search element < middle element reset the right boundary to the index just before middle element otherwise reset the left boundary to the index just after middle element.
• Repeat the above process until the size of sub-arrays reduces to zero.
• If the element doesn't exist then `return` 0 as the last statement in the `function`
• In the main section call the `function` with a sorted array, search value, and `cat` the results according to the `return` value from the `function`

Now, let's see the working of the Binary Search Algorithm. Take an array (4, 0, 3, 1, 5, 6, 2) and search element 4. Sort the array (0, 1, 2, 3, 4, 5, 6). We have 0 at the start,6 at last, and 3 at the middle, check if the middle one is 4. It's not, also search value 4 is greater than middle element 3 so now the list to search becomes (4,5,6) i.e., the right subarray. Here the middle element is 5, choose the left subarray which is (4). We got a match so return the index of 4. Thus our search became successful.

ALGORITHM

STEP 1: Write a `function` binarySearch() with variables array arr and search value item.

STEP 2: Initialise variables low 0 and high last index

STEP 3: Start a `while loop` to repeat until the condition low<=high,

STEP 4: Find the middle index of the array mid and check the middle element with the item, if matches `return `index of the middle element

STEP 5: Check if item<arr[mid] then last index becomes high=mid-1 else start index becomes low=mid+1

STEP 6: Now end the `function` by `return` 0 means no match found

STEP 7: Initialise an array arr with values and item to be searched

STEP 8: Sort the array and call the binarySearch() with values arr, item and check the `return `value and `cat `the suitable result

R Source Code

```                                          ```binarySearch = function(arr,item) {
low <- 1; high <- length(arr)
while (low <= high){
mid <- as.integer(round((low + high) / 2))
if (abs(arr[mid] - item) ==0) {
return(mid)
} else if (arr[mid] < item) {
low <- mid + 1
} else {
high <- mid - 1
}
}
return(0)
}
arr <- c(4, 0, 3, 1, 5, 6, 2)
sorted_arr <- sort(arr)
item <- 4
cat("Array ", arr, "\nSorted array ",sorted_arr,"\nitem = ", item, "\n")
index <- binarySearch(sorted_arr, item)
if (index!=0){
cat("Element is present at index ", index, "\n")
}else{
}```
```

OUTPUT

```Array  4 0 3 1 5 6 2
Sorted array  0 1 2 3 4 5 6
item =  4
Element is present at index  5 ```
VIEW ALL
VIEW ALL
VIEW ALL