Write a Binary Search program
- 7 Answers
- 25313 Views
- Microsoft, TCS, I also Faced
- E-Mail Answers
Answers were Sorted based on User's Feedback
#include<conio.h>
#include<iostream.h>
#include<process.h>
int binarysearch(int list[], int end, int target, int &locn)
{
int first=0, mid, last=end;
while(first<=last)
{
mid=(first+last)/2;
if(target>list[mid])
first=mid+1;
else if(target<list[mid])
last=mid-1;
else
break;
}
locn=mid+1;
return(target==list[mid]);
}
void main()
{
int a[10],i,s=0,n,loc,flag=0;
clrscr();
cout<<"\n Enter the no. of element to store:\n";
cin>>n;
cout<<"Enter the Elements:\n";
for(i=0;i<n;i++)
cin>>a[i];
cout<<"\n The Elements are:\n";
for(i=0;i<n;i++)
cout<<a[i]<<"\t";
cout<<"\n Enter the Element to search:\n";
cin>>s;
if(binarysearch(a,n,s,&loc))
cout<<"\nThe element "<<s<< " is available at location
"<<loc<<endl;
else
cout<<"\nThe element "<<s<< " is not found in the List"<<endl;
}
| Is This Answer Correct ? | 51 Yes | 23 No |
Answer / jamshed
SHORTEST BINARY SEARCH PROGRAM
import java.io.*;
class Binary
{
public static void main()throws IOException
{
InputStreamReader isr=new
InputStreamReader(System.in);
BufferedReader br=new BufferedReader(isr);
int a[]={5,7,9,11,15,20,30,45,89,97};
int n,c=0,l=0,u=9,m;
System.out.println("Enter a Number to Search");
n=Integer.parseInt(br.readLine());
while(u>l)
{
m=(l+u)/2;
if(a[m]==n)
{
c++;
break;
}
else if(a[m]>n)
u=m;
else if(a[m]<n)
l=m+1;
}
if(c==0)
System.out.println("Not Found");
else
System.out.println("Found");
}
}
| Is This Answer Correct ? | 14 Yes | 4 No |
Answer / s.devudu
#include<stdio.h>
int binarysearchr(int a[],int,int,int);
void main()
{
int a[],i,j,b,n,key,temp;
clrscr();
printf("enter the n value");
scanf("%d",&n);
printf("enter the array values");
for(i=0;i<=n;i++)
scanf("%d",&a[i]);
for(i=0;i<=n;i++)
{
for(j=0;j<=n-1;j++)
{
if(a[j]>=a[j+1])
{
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
}
printf("in an array after sorting");
scanf(%d\t",&a[i]);
printf("enter the key value");
for(i=0;i<=n;i++)
scanf(%d",&key);
b=binarysearchr(int a[],int i,int n,int key);
if(b)
printf("location of key element is %d\n",b);
else
printf("key not found");
getch();
}
int binarysearchr(int a[],int low,int high,int key);
{
int mid;
if(low>high)
return 0;
mid=(low+high)/2;
if(key==a[mid])
return mid;
else if(key<=a[mid])
return binarysearchr(a,mid-1,high,key);
else
reurn binarysearch(a,low,mid+1,key);
}
| Is This Answer Correct ? | 4 Yes | 2 No |
Answer / shah varshil
#include<stdio.h>
main()
{
int c, first, last, middle, n, search, array[100];
printf("Enter number of elements\n");
scanf("%d",&n);
printf("Enter %d integers\n", n);
for ( c = 0 ; c < n ; c++ )
scanf("%d",&array[c]);
printf("Enter value to find\n");
scanf("%d",&search);
first = 0;
last = n - 1;
middle = (first+last)/2;
while( first <= last )
{
if ( array[middle] < search )
first = middle + 1;
else if ( array[middle] == search )
{
printf("%d found at location %d.\n", search, middle
+1);
break;
}
else
last = middle - 1;
middle = (first + last)/2;
}
if ( first > last )
printf("Not found! %d is not present in the list.\n",
search);
return 0;
}
| Is This Answer Correct ? | 2 Yes | 0 No |
Answer
# 1 #include<conio.h>
#include<iostream.h>
#include<process.h>
int binarysearch(int list[], int end, int target, int &locn)
{
int first=0, mid, last=end;
while(first<=last)
{
mid=(first+last)/2;
if(target>list[mid])
first=mid+1;
else if(target<list[mid])
last=mid-1;
else
break;
}
locn=mid+1;
return(target==list[mid]);
}
void main()
{
int a[10],i,s=0,n,loc,flag=0;
clrscr();
cout<<"\n Enter the no. of element to store:\n";
cin>>n;
cout<<"Enter the Elements:\n";
for(i=0;i<n;i++)
cin>>a[i];
cout<<"\n The Elements are:\n";
for(i=0;i<n;i++)
cout<<a[i]<<"\t";
cout<<"\n Enter the Element to search:\n";
cin>>s;
if(binarysearch(a,n,s,&loc))
cout<<"\nThe element "<<s<< " is available
at location
"<<loc<<endl;
else
cout<<"\nThe element "<<s<< " is not found
in the List"<<endl;
}
| Is This Answer Correct ? | 21 Yes | 20 No |
Answer / saisharath
#include<stdio.h>
#include<conio.h>
int nr_bin_search(int[],int,int);
void main()
{
int key,i,n,index,l[20];
printf("\n enter the number of elements in the list:");
scanf("%d",n);
printf("\n enter the elements of the list:");
for(i=0;i<n;i++)
scanf("%d",&l[i]);
printf("\n enter the key element to be searched in the
list:");
scanf("%d",&key);
index=nr_bin_search(l,n,key);
if(index==-1)
printf("\n search completed,element%d found in the list at
position %d",key,index);
getch();
}
int nr_bin_search(ints[],int n,int e)
{
int low_val,mid_val,high_val;
low_val=0;
high_val=0;
while(high_val>=low_val)
{
mid_val=(low_val+high_val)/2;
if(s[mid_val]==e)
return(mid_val);
if(s[mid_val]<e)
low_val=mid_val+1;
else
high_val=mid_val-1;
}
return-1;
}
| Is This Answer Correct ? | 11 Yes | 13 No |
Answer / jerry prince
Option Explicit
'
' Student record user defined type.
'
Private Type tStud
RegNO As String * 9
ContactAddress As String * 40
StudentName As String * 30
Phone As String * 24
Sex As String * 10
End Type
'
' Array of students
'
Private StudArray() As tStud
Private StudRec As tStud
Private RecCt As Long
Private Sub cmdQuit_Click()
End
End Sub
Private Sub cmdSearchArray_Click()
Dim lngMatch As Long
'
' Search the array for a record.
'
lngMatch = fSearchArray(txtNO)
'
' If found, display the record.
'
If lngMatch Then
Call pShowArrayRecord(lngMatch)
Else
Call ClearRecord
End If
End Sub
Private Sub cmdSearchFile_Click()
Dim lngMatch As Long
'
' Search the file for a record.
'
lngMatch = fSearchFile(txtNO)
'
' If found, display the record.
'
If lngMatch Then
Call pShowFileRecord(lngMatch)
Else
Call ClearRecord
End If
End Sub
Private Sub Form_Load()
Dim GetStud As tStud
Dim l As Long
'
' Load an array with data from the file and
' load the listbox with the Reg NO from each record.
'
Open "StudList.dat" For Random As 1 Len = Len(GetStud)
RecCt = LOF(1) / Len(GetStud)
ReDim StudArray(1 To RecCt)
For l = 1 To RecCt
Get 1, l, StudArray(l)
lstRegNO.AddItem StudArray(l).RegNO
Next
Close 1
End Sub
Private Sub pShowArrayRecord(lngRecord As Long)
'
' Display a record from the array in the textboxes.
'
txtRegNO = StudArray(lngRecord).RegNO
txtContactAddress = StudArray(lngRecord).ContactAddress
txtStudentName = StudArray(lngRecord).StudentName
txtPhone = StudArray(lngRecord).Phone
txtSex = StudArray(lngRecord).Sex
End Sub
Private Sub pShowFileRecord(lngRecord As Long)
'
' Display a record from the file in the textboxes.
'
txtRegNO = StudRec.RegNO
txtContactAddress = StudRec.ContactAddress
txtStudentName = StudRec.StudentName
txtPhone = StudRec.Phone
txtSex = StudRec.Sex
End Sub
Private Sub ClearRecord()
'
' Clear the text boxes
'
txtRegNO = ""
txtContactAddress = ""
txtStudentName = ""
txtPhone = ""
txtSex = ""
End Sub
Private Sub Form_Unload(Cancel As Integer)
Erase StudArray
Set frmSearch = Nothing
End Sub
Private Sub lstRegNO_Click()
'
' Display the selected listbox item in the textbox.
'
txtNO = lstRegNO.Text
End Sub
Private Function fSearchArray(strSearchItem As String) As Long
Dim lngFirst As Long
Dim lngLast As Long
Dim lngMiddle As Long
Dim lngLastPass As Long
Dim strItem As String
Dim strValue As String
Dim blnDone As Boolean
'
' Search an array for an item using a binary search.
' The search is not case sensitive.
' Returned is the index of the matching array element.
'
'
' Initialize the pointers to the first
' and last records.
'
lngFirst = 1
lngLast = UBound(StudArray)
strItem = UCase$(Trim$(strSearchItem))
'
' If only one record, see if it is the desired one.
'
If lngLast = 1 Then
If strItem = UCase$(StudArray(1).RegNO) Then
fSearchArray = 1
Else
fSearchArray = 0
End If
Exit Function
End If
'
' Set the pointer to the middle record.
'
lngMiddle = ((lngLast - lngFirst) + 1) \ 2
'
' Apply the binary search criteria until the
' item is found or the list is exhausted.
'
Do Until blnDone
strValue = UCase$(StudArray(lngMiddle).RegNO)
If strItem = strValue Then
'
' Found it.
'
fSearchArray = lngMiddle
blnDone = True
Exit Do
ElseIf strItem < strValue Then
'
' Direction = down
' Remove the second half of the list.
'
lngLast = lngMiddle
lngMiddle = lngMiddle - ((lngLast - lngFirst) +
1) \ 2
ElseIf strItem > strValue Then
'
' Direction = Up
' Remove the first half of the list.
'
lngFirst = lngMiddle
lngMiddle = lngMiddle + ((lngLast - lngFirst) +
1) \ 2
End If
'
' See if list is still divisible.
'
If (lngMiddle = lngFirst) Or (lngMiddle = lngLast) Then
lngLastPass = lngLastPass + 1
If lngLastPass = 2 Then
lngLastPass = 0
fSearchArray = 0
blnDone = True
End If
End If
Loop
End Function
Private Function fSearchFile(strSearchItem As String) As Long
Dim lngFirst As Long
Dim lngLast As Long
Dim lngMiddle As Long
Dim lngLastPass As Long
Dim strItem As String
Dim strValue As String
Dim blnDone As Boolean
Open "StudList.dat" For Random As 1 Len = Len(StudRec)
RecCt = LOF(1) / Len(StudRec)
'
' Search a file for an item using a binary search.
' The search is not case sensitive.
' Returned is the index of the matching file element.
'
'
' Initialize the pointers to the first
' and last records.
'
lngFirst = 1
lngLast = RecCt
strItem = UCase$(Trim$(strSearchItem))
'
' If only one record, see if it is the desired one.
'
If lngLast = 1 Then
Get 1, 1, StudRec
If strItem = UCase$(StudRec.RegNO) Then
fSearchFile = 1
Else
fSearchFile = 0
End If
Close 1
Exit Function
End If
'
' Set the pointer to the middle record.
'
lngMiddle = ((lngLast - lngFirst) + 1) \ 2
'
' Apply the binary search criteria until the
' item is found or the file is exhausted.
'
Do Until blnDone
'
' Read a record from the file.
'
Get 1, lngMiddle, StudRec
strValue = UCase$(StudRec.RegNO)
If strItem = strValue Then
'
' Found it.
'
fSearchFile = lngMiddle
blnDone = True
Exit Do
ElseIf strItem < strValue Then
'
' Direction = down
' Remove the second half of the file.
'
lngLast = lngMiddle
lngMiddle = lngMiddle - ((lngLast - lngFirst) +
1) \ 2
ElseIf strItem > strValue Then
'
' Direction = Up
' Remove the first half of the file.
'
lngFirst = lngMiddle
lngMiddle = lngMiddle + ((lngLast - lngFirst) +
1) \ 2
End If
'
' See if file is still divisible.
'
If (lngMiddle = lngFirst) Or (lngMiddle = lngLast) Then
lngLastPass = lngLastPass + 1
If lngLastPass = 2 Then
lngLastPass = 0
fSearchFile = 0
blnDone = True
End If
End If
Loop
Close 1
End Function
Private Sub txtID_KeyPress(KeyAscii As Integer)
'
' Convert to upper case.
'
KeyAscii = Asc(UCase$(Chr(KeyAscii)))
End Sub
| Is This Answer Correct ? | 4 Yes | 12 No |
What are the disadvantages of linked list over array?
Can we store null in arraylist?
What is the difference between classifying and sorting?
What is difference between hashmap and linkedhashmap?
There is a program which inserts and deletes node in a sorted singly linked list. There is a bug in one of the modules, how would you debug it?
What is time complexity of sorting algorithms?
Why is map not a collection?
What is the use of substring?
What is the difference between hashset and treeset?
To describe the Complexity of Binary search, Quicksort and various other sorting and searching techniques..
0 Answers HPCL, Hughes Systique Corporation,
What are all the classes and interfaces that are available in the collections?
When is a binary search algorithm best applied?
Windows 
