Binary search in array in c?

Answer 1

// answer in C-style pseudo-code

// all division should be rounded up

// search will return the index of the number found, or -1 if it was not found

// nums is the array of numbers we're searching through

// num is the specific number we want to find in nums

// current is the index we are currently inspecting

// start is the first index of nums (typically 0)

// end is the last index of nums (typically the length - 1)

// preconditions: nums must be sorted or function is nondeterministic

int search( int[] nums, int num, int current, int start, int end ) {

if( nums[current] end ) { // target not in list

return -1;

}else if( nums[current] > num ) { // search to the left

return search( nums, num, current - ((current - start)/2), start, current );

}else if( nums[current] < num ) { // search to the right

return search( nums, num, current + ((end - current)/2), current, end );

}

}

// convenience function to start the search

int search( int[] nums, int num ) {

return search(nums, num, (nums.length/2), 0, nums.length - 1);

}

Answer 2

#include

#include

void main()

{

int num,i,ar[20],m,low,high,mid,pos=1;

clrscr();

printf("Enter any number of element you want to insert=\t");

scanf("%d",&num);

printf("enter the list in non incresing order \n");

for(i=0;i

{

scanf("%d",&ar[i]);

}

printf("please enter the number you want to search\t");

scanf("%d",&m);

low=0;

high=num-1;

do

{

mid=(low+high)/2;

if(m

high=mid-1;

else if(m>ar[mid])

low=mid+1;

}while(m!=ar[mid]&&low<=high);

if(m==ar[mid])

{

printf("\nsearch sucessful");

}

else

{

printf("\nsearch unsuccessful");

}

getch();

}

iamr college of engineering

(rahul chaudhary)

cse branch(mail me at jaatchaudhary4@gmail.com)

Answer 3

To perform a binary search upon an array, the array elements must be in sorted order.

int search (int value, int a[], const int size)

{

/*

returns the index of the given value,

or -1 if the value does not exist

*/

int left=0;

int right=size;

while (left<right)

{

int mid = (right-left)/2 + left;

if (a[mid]==value)

return mid;

else if (a[mid]<value)

left=mid+1;

else

right=mid;

}

return -1;

}

Answer 4

The following program demonstrates binary search. Note that binary search only works with sorted data. To compare the performance, we'll use a standard linear search using unsorted data first, followed by a binary search on the same data in sorted order. The search functions will tell us how many elements had to be compared to locate the value. In rare cases a linear search may prove faster if the value being sought just happens to be near the start of the data. However, when a value cannot be found, the binary search is clearly faster since a linear search must search every element, whereas a binary search reduces the remaining data to be searched by half after each comparison.

Note that although it's easy to assume you need a binary tree to perform a binary search this is not the case at all. In order to search efficiently, you need a balanced binary tree and the simplest way of achieving that is with a sorted array. The middle element of a sorted array is the root of a binary tree and all searches begin there. If the value is not in the root, it must be in the left sub-array (if it is less) or the right sub-array (if it is greater), but each half of the array is simply a smaller binary tree where the middle element is the root of that tree. So by recursively comparing the roots you will either locate the value (in which case you are done) or you will end up with an empty sub-array (in which case the value does not exist).

To perform a binary search upon an array you need to keep track of the left and right indices of the sub-array. Initially these will represent the lower and upper bounds of the entire array. From these indices you can calculate the middle index. When you know which half of the sub-array your value resides, you move the left or right bound accordingly. Thus if the value is in the lower half, the right index becomes middle - 1, otherwise the left index becomes middle + 1. You then recalculate the middle index and continue searching. If left becomes greater than right then you have an empty sub-array so the value does not exist.

#include<iostream>

#include<iomanip>

#include<vector>

#include<algorithm>

#include<random>

#include<time.h>

void initialise (std::vector<unsigned>& data)

{

// Pseudo-random number generator (range: 1 to 99).

std::default_random_engine generator;

generator.seed ((unsigned) time (NULL));

std::uniform_int_distribution<unsigned> distribution (1, 99);

data.clear();

unsigned max_elements(50);

while (max_elements--)

data.push_back (distribution (generator));

}

int linear_search(std::vector<unsigned>& data, unsigned value, unsigned& comparisons)

{

int index(-1);

for( comparisons=0; comparisons<data.size() && index<0; ++comparisons)

if (data[comparisons] -1)

{

std::cout << "not found. ";

}

else

{

std::cout << "found at index " << binary_index << ". ";

}

std::cout << "Comparisons: " << binary_comparisons << std::endl;

}

}

Answer 5

include<stdio.h>

#include<conio.h>

void main()

{

int a[10],n,i,j,temp;

int beg,end,mid,target;

clrscr();

printf("enter the total numbers:");

scanf("%d",&n);

printf("enter the array elements:" );

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

scanf("%d",&a[i]);

for(i=0;i<n-1;i++)

{

for(j=0;j<n-i-1;j++)//for sorting the elements

{

If(a[j+1]<a[j])

{

temp=a[j];

a[j]=a[j+1];

a[j+1]=temp;

}

}

}

printf("the sorted numbers are:");

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

printf("%4d",a[i]);

beg=a[0];

end=a[9];

mid=(beg+end)/2;

printf("\nenter the number to be searched:");

scanf("%d",&target);

while(beg<=end && a[mid]!=target)//for searching the element in a sorted array

{

if(target<a[mid])

end=mid-1;

else

beg=mid+1;

mid=(beg+end)/2;

}

If(a[mid]==target)

{

printf("\nthe number is found at position %2d",mid);

}

else

{

printf("\nthe number is not found:");

}

getch();

}

Answer 6

C program for Performing Binary Search

http://thingsoverflow.com/?p=211