/*condition for binary search is this that... u have to use sorted array & u should know size of array in which element is to be searched otherwise do sorting 1st*/
#include<stdio.h>
int main()
{
int search,x,r,s;
int hi=10,lw=0,mid=0,i,k,proceed;
int arr[10];//={3,5,9,7,2,16,13,14,12,17};
int arr1[10];
for(k=0;k<10;k++)
{
printf("\nGIVE ME ARRAY:");//i had made input elements into old array ...before using binary searching ..i have to sort the array....
scanf("%d",&arr[k]);
}
for(r=0;r<10;r++)//every element in old array ...is compared to new array atmost 9 times & atleast upto the position where new array element is grater than old array element ..upto the position where we have to place our old array element which is small .than of all new array elements...& make new array as ascending order array....
{
for(s=0;s<=r;s++)//each element of old array is compared to new array elements atmost no. of old array elements.i.e. max no. comprisions could be upto no. of elemets in old array....& atleast..upto when elements of old array arealready be inserted in new array...compressions takes place upto then....
{
if(arr[r]<arr1[s])//at the point of value of r & s,,,when old array element is smaller than new array element...then attempt to put it at that posiotion
{
x=r;//r is total no. of elements in old array
x--;//bcz.. elements starts from 0 ..so loop will take place for 1 less no. of elements
for(;s<=x;x--)//shift all other elements which are on right side ..which are all greater elements in new array than element of old array ...
//where 1st element in new array is found greater ...after which all elements in new array are greater...
//that 1st posiotion where 1st element in new array is found greater ...upto that position ..elements which are greater in new array .,,all are shifted to right 1 by 1....upto this position where 1st element of new array was found greater..
//then place that smaller element of old array into new array into this position will make again new array into ascending array
//in this way we will search ...position of each element using loop of s...1 by 1 ..& put that element at its right place ...to make array in ascending order
{
arr1[x+1]=arr1[x];//shift position of new array's greater elements than element to be inserted...1 by 1..//5 to 6 //4 to 5// 3 to 4// 2 to 3//
arr1[s]=arr[r];//suppose i have to put element at pos 2...arr[r] is smaller than all other elements in new array which are shifted to right ..//
printf("\narr[%d]=%d",s,arr1[s]);//INSERTION INTO NEW ARRAY IS DONE AFTER SORTING
break;//when assignment takes place ...then break from loop of s ...back into loop of r again
}
}
if(arr1[s] != arr[r])
{
arr1[s-1]=arr[r];//optional
s=0;
}
}
for(s=0;s<=r;s++)
{
printf("\nfinal arr1[%d]=%d",s,arr1[s]);//now we will obtain new array into sorted form ...
}
i=hi;
for(proceed=0;i>1;proceed++)//inti then cond check ....back......1st it inc.then check cond.
{
i=i/2;//count no. of iterations which should take in next loop while binary searching
////proceed=0 i=10 ;proceed=1 10/2=5;proceed=2 5/2=2;proceed=3 2/2=1;i<1 failed out of loop
// //pro=3
}
printf("\nproceed=%d",proceed);////value of procceed calculated will tell us how many no. of max.iterations will required while searching a perticular elements ;it totally depends on no. of elements r present in array..
hi=10;lw=0;///for 2nd,3rd or more no. of element searching hi should be start by 10 & lw should be 0
mid=(hi+lw)/2;////mid =5 or again & again started from 5
for(i=0;i<proceed;i++)//loop should operate at 0,1& 2 times.
{
//mid=(hi+lw)/2;
if(arr1[mid]>search)///1st time arr[5]>search
{
hi=mid;//if mid element is greater then element to be searched ;it means element to be searched will found in lower half part of array;then lw=0 as it is & mid is to be *made hi
mid=(lw+hi)/2;////again mid is found by adding this (lw which has old mid value to hi)/2
}
else if(arr1[mid]<search)//
{
lw=mid;//now func will work in else for these initialised values.
////if arr[mid] is less than element to be searched ;it means element lies in upper half part//then mid will work as lower elemENT
mid=(lw+hi)/2;//7th pos=14//again come back at 8th pos
//printf("\nmid in else if=%d",mid);
}
if(arr1[mid]==search)//by using else if here one loop will proceed extra again by proceed=3 value.
{
printf("\nsearched at %d pos",mid);////once element is found ;;it is printed ;;no extra loop will operate..
break;
}
}
}while(search != 0);////it will 1st search 0 element in array if found it will print its pos then it will go out of while loop
