SE and Programming 2090- Extra Work for Practice Write a function in Haskell to

Question

SE and Programming 2090- Extra Work for Practice

Write a function in Haskell to do the following...

Recursive Binary Search - binary_search(data, item, offset)

Takes a sorted list, data, and performs a recursion binary search of data for the element item.  If found, returns the index where the item is found. If not found, returns –1.  offset is a variable used for recursive calls to record the offset from the original data. The function will always be initially called with this set to 0. You are permitted to use the following functions:

take n alist - returns, as a list, the first n items in an alist

drop n alist = returns a list without the first n items of alist

quot num divisor - returns the quotient of num / divisor

length alist - returns the length of a list

mathematical/comparison operations (+, -, <, etc.)

!! - list index operator

Template:

Examples:

module Function where import Data.List import Data.Maybe binary_search list item offset = Nothing -- fill in

Explanation / Answer

// Example taken for the C program to perform the binary serach operation
#include <stdio.h>

// This is a recursive binary search function which
//returns location of x in given array arr[l..j] is present,
// otherwise -1
int binarySearch(int arr[], int i, int j, int x)
{
if (j >= i)
{
int mid = i + (j - i)/2;

// first check if the element is present at the middle
// itself
if (arr[mid] == x)  
return mid;

// If element is smaller than mid, then
// it can only be present in left subarray
if (arr[mid] > x)
return binarySearch(arr, i, mid-1, x);

// Else the element can only be present
// in right subarray
return binarySearch(arr, mid+1, j, x);
}

// We reach here when element is not
// present in array
return -1;
}

int main(void)
{
int arr[] = {2, 3, 4, 10, 40};
int n = sizeof(arr)/ sizeof(arr[0]);
int x = 10;
int result = binarySearch(arr, 0, n-1, x);
(result == -1)? printf("Element is not present in array")
: printf("Element is present at index %d",
result);
return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.