Scribd
Upload
59 views

Linear and Binary Search

The document contains 4 code snippets demonstrating different approaches to searching arrays: 1) Linear search to find all occurrences of a value 2) Binary search using recursion to find a value 3) Binary search without recursion to find a value 4) Another binary search example to find a value Each snippet is labeled as input and followed by output, but no output is shown. The snippets implement various searching algorithms on arrays.

Uploaded by

Lavanya Sinha
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
59 views

Linear and Binary Search

The document contains 4 code snippets demonstrating different approaches to searching arrays: 1) Linear search to find all occurrences of a value 2) Binary search using recursion to find a value 3) Binary search without recursion to find a value 4) Another binary search example to find a value Each snippet is labeled as input and followed by output, but no output is shown. The snippets implement various searching algorithms on arrays.

Uploaded by

Lavanya Sinha
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 6

Name: Lavanya Sinha

PRN: 21070122086
CSB-1

1. INPUT

Linear search (multiple occurencies)


#include <stdio.h>

int main()
{
int array[100], search, c, n, count = 0;

printf("Enter number of elements in array\n");


scanf("%d", &n);

printf("Enter %d numbers\n", n);

for (c = 0; c < n; c++)


scanf("%d", &array[c]);

printf("Enter a number to search\n");


scanf("%d", &search);

for (c = 0; c < n; c++) {


if (array[c] == search) {
printf("%d is present at location %d.\n", search, c+1);
count++;
}
}
if (count == 0)
printf("%d isn't present in the array.\n", search);
else
printf("%d is present %d times in the array.\n", search, count);

return 0;
}
OUTPUT

2. INPUT
Binary search (recursion)
#include <stdio.h>

int binarySearch(int array[], int x, int low, int high) {


if (high >= low) {
int mid = low + (high - low) / 2;

if (array[mid] == x)
return mid;

if (array[mid] > x)
return binarySearch(array, x, low, mid - 1);
return binarySearch(array, x, mid + 1, high);
}

return -1;
}

int main(void) {
int array[] = {3, 4, 5, 6, 7, 8, 9};
int n = sizeof(array) / sizeof(array[0]);
int x = 4;
int result = binarySearch(array, x, 0, n - 1);
if (result == -1)
printf("Not found");
else
printf("Element is found at index %d", result);
}

OUTPUT

3. BINARY SEARCH (without recursion)


#include <stdio.h>
int binarySearch(int array[], int x, int low, int high) {

while (low <= high) {


int mid = low + (high - low) / 2;

if (array[mid] == x)
return mid;

if (array[mid] < x)
low = mid + 1;

else
high = mid - 1;
}

return -1;
}

int main(void) {
int array[] = {3, 4, 5, 6, 7, 8, 9};
int n = sizeof(array) / sizeof(array[0]);
int x = 4;
int result = binarySearch(array, x, 0, n - 1);
if (result == -1)
printf("Not found");
else
printf("Element is found at index %d", result);
return 0;
}

OUTPUT
4. INPUT
Binary search

#include <stdio.h>

int binarySearch(int array[], int x, int low, int high) {


// Repeat until the pointers low and high meet each other
while (low <= high) {
int mid = low + (high - low) / 2;

if (array[mid] == x)
return mid;

if (array[mid] < x)
low = mid + 1;

else
high = mid - 1;
}

return -1;
}

int main(void) {
int array[] = {3, 4, 5, 6, 7, 8, 9};
int n = sizeof(array) / sizeof(array[0]);
int x = 4;
int result = binarySearch(array, x, 0, n - 1);
if (result == -1)
printf("Not found");
else
printf("Element is found at index %d", result);
return 0;
}

OUTPUT

You might also like