Write an Array proram In Binary search with taking inputs from the user
Answers
Answer:
import java.util.Scanner;
public class BinarySearchExample{
public static void main(String args[])
{
//taking inputs from user array,item to found
int n, key;
Scanner sc = new Scanner(System.in);
System.out.println("Enter number of elements:");
n = sc.nextInt();
int[] arr = new int[n];
System.out.println("Enter " + n + " integers");
for (int i= 0; i< n; i++)
arr[i] = sc.nextInt();
System.out.println("Enter the search value:");
key = sc.nextInt();
//now sorting it in ascending order
int temp = 0;
for(int i=0; i < n; i++)
for(int j=1; j < (n-i); j++)
if(arr[j-1] > arr[j])
{
temp = arr[j-1];
arr[j-1] = arr[j];
arr[j] = temp;
}
//printing sorted array
System.out.println("your array is");
for (int i= 0; i< n; i++)
System.out.print(arr[i]+" ");
//now binary search is performed
int first=0;
int last=n-1;
int mid = (first + last)/2;
while( first <= last ){
if ( arr[mid] < key )
{
first = mid + 1;
}
else if ( arr[mid] == key )
{
System.out.println("Element is found at index: " + (mid+1));
break;
}
else
{
last = mid - 1;
}
mid = (first + last)/2;
}
if ( first > last ){
System.out.println("Element is not found!");
}
} }
Explanation:
first of all let's know basics of binary search
first compulsion is it should be arranged in asending or descending order then only we can perform binary search ;you will see it later
here we have arranged it in ascending order using bubble sort technique
in it we compare each value at i th and i+1 th position if i th one is greater than i+1 th then we swap the values every time ;we iterate it for n + n-1 + n-2 + .... times by nested loops i.e external loop is fixed for n times and inner loop runs every time 1 less than previous iteration..
at first iteration highest value reach last index and in second iteration second largest value reach second last index and so on...
now coming back to binary search,
suppose array is 2 6 13 25 29 45 78 and we have to search for 78
main logic of binary search is we divide array in two parts from middle
here middle one is 25
now it will check if item==25
no it's not.......
now it will check whether item is less than middle term or greater
if it's greater than middle term ,then we have to search in latter part of array
else
we have to see in index less than middle one.
here, 78>25 so we have to see in latter part of array
now, remaining array is of 3 elements 29 45 78
again we will search for middle element
that's 45
check if it's equal to item
oops again it's not
so now we know what we have to do
again check whether it's smaller or bigger
45<78
so,let's check for higher index
now array left 78
middle term is only term
let's check for it
78==78
yup we did it
we found it
now print the index
now we delve into our program
variable first contains index of first element of array every time we divided it will change if item to be found is greater than middle term
and variable last contains last index of element and it will change when item is less than middle term
suppose we feed a value that's not in the array
then,
it will search for it till it reach last element
and now mid=last=first
and if still it couldn,t find it ...then first will be greater than last according to program
and that's not possible so it will print not found
and all these comparison we can perform only when it's arranged in order otherwise not
Best way to understand it is take 2-3 array of 7-8 elements and try to dry run
if you are able to reach the index or not
Hope you understand it
Wishing you best luck for exams
Feel free to ask any doubt:-)