How to revise a binary search algorithm to handle a dupilcate in the array. Pret
ID: 672650 • Letter: H
Question
How to revise a binary search algorithm to handle a dupilcate in the array. Pretty much to return the smallest index of all index matches.
Code:
int search(int data[], int value, int low, int high){
if (low > high)
return -1;
int mid =(low + high)/2;
if (data[mid] == value)
return search(data, value, low, mid - 1);
else if (data[mid] < value)
return search(data, value, mid +1, high);
}
Im not looking for a exact answer, because I would like to learn and write this myself. Hoping for steps to tackle this or puesdo code. Thank you for any help you can give
Explanation / Answer
Binary Search Algorithm
Modified Pseudocode for binary search
int binarySearch(int arr[], int left, int right, int searchvalue)
{
while (left <= right)
{
int mid = (left + right)/2;
if (arr[mid] == searchvalue) return mid; // Check if x is present at mid
if (arr[mid] < searchvalue) l = mid + 1; // If x greater, ignore left half
else r = m - 1; // If x is smaller, ignore right half
}
return -1; // if we reach here, then element was not present
}
Binary.c
#include <stdio.h>
int binarySearch(int arr[], int l, int r, int x)
{
while (l <= r)
{
int m = (l + r)/2;
if (arr[m] == x) return m; // Check if x is present at mid
if (arr[m] < x) l = m + 1; // If x greater, ignore left half
else r = m - 1; // If x is smaller, ignore right half
}
return -1; // if we reach here, then element was not present
}
int main(void)
{
int arr[] = {2, 3, 4, 10, 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
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.