Computer Science, asked by prap444pdejk6, 1 year ago

Write an Array proram In Binary search with taking inputs from the user

Answers

Answered by sswaraj04
1

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:-)


prap444pdejk6: Bro last help
prap444pdejk6: Can u send me bubble sort and selection sort program
prap444pdejk6: Bro no need to type it
prap444pdejk6: If u had saved it means only send
prap444pdejk6: Otherwise no need bro beacuse it is unnecessary stress for u
sswaraj04: bubble sort is already there in the program
sswaraj04: just delete last segment of searching
sswaraj04: amd it will br bubble sort program
sswaraj04: be*
prap444pdejk6: k bro
Similar questions