Java Program for Binary Search
From Wikipedia
In computer science, binary search, also known as half-interval search, logarithmic search, or binary chop, is a search algorithm that finds the position of a target value within a sorted array. Binary search compares the target value to the middle element of the array; if they are unequal, the half in which the target cannot lie is eliminated and the search continues for the remaining half until it is successful or the remaining half is empty.
This search method uses low and high positions and matches with the middle element. The array must be in sorted order and low and high positions are changed in order to search the given data(mid = (low + high) / 2. If the given value is less than mid-value then high = mid - 1. If the value is greater then mid-value then low = mid + 1 and if the given value is equal to the mid-value then the search result found and printed.
The time complexity of the above algorithm is O(n).
Java Program
Binary Search with Number
import java.util.*;public class BinarySearch
{
public static void main(String arg[])
{
int n[]={1,4,6,7,8,9,10,11,14,15,16};
int low, high, mid, p=0, l, i, m, f=0;
l=n.length;
low=0;
high=l;
Scanner sc=new Scanner(System.in);
System.out.println("Enter number to search:");
m=sc.nextInt();
while(low<=high)
{
mid=(low+high)/2;
if(m<n[mid])
high=mid-1;
else if(m>n[mid])
low=mid+1;
else if(m==n[mid])
{
f=1;
p=mid+1;
break;
}
}
if(f==1)
{
System.out.println(m+" is located at "+p);
}
else
{
System.out.println(m+" is not found");
}
}
}
Binary Search with String
import java.io.*;
public class BinarySearchWithSorting
{
public static void main(String args[]) throws IOException
{
String name[] = new String[20];
String s, t;
int i,f=0,j;
int low, high, mid, pos;
InputStreamReader in=new InputStreamReader(System.in);
BufferedReader br=new BufferedReader(in);
System.out.println("Enter 20 Names in array:");
for(i=0;i<20;i++)
{
name[i] = br.readLine();
}
System.out.println("Enter name to Search:");
s = br.readLine();
// Sorting of array
for(i=0;i<19;i++)
{
for(j=0;j<19-i;j++)
{
if(name[j].compareTo(name[j+1])>0)
{
t = name[j];
name[j] = name[j+1];
name[j+1] = t;
}
}
}
System.out.println("Sorted array:");
for(i=0;i<20;i++)
{
System.out.print(name[i] + " ");
}
// Binary Search
high=20;
low=0;
pos=0;
while(low <= high)
{
mid = (low + high) / 2;
if(s.compareTo(name[mid])<0)
{
high = mid - 1;
}
else if(s.compareTo(name[mid])>0)
{
low = mid + 1;
}
else if(s.compareTo(name[mid])==0)
{
pos = mid + 1;
break;
}
}
System.out.println("\n Search result");
System.out.println(s+" is located at " + pos);
}
}
