Search in an almost sorted array

Search in an almost sorted array

Given an array which is sorted, but after sorting some elements are moved to either of the adjacent positions, i.e., arr[i] may be present at arr[i+1] or arr[i-1]. Write an efficient function to search an element in this array. Basically the element arr[i] can only be swapped with either arr[i+1] or arr[i-1].
For example consider the array {2, 3, 10, 4, 40}, 4 is moved to next position and 10 is moved to previous position.
Example:

Input: arr[] =  {10, 3, 40, 20, 50, 80, 70}, key = 40
Output: 2 
Output is index of 40 in given array

Input: arr[] =  {10, 3, 40, 20, 50, 80, 70}, key = 90
Output: -1
-1 is returned to indicate element is not present

my sollution is


#include<stdio.h>

int main(void)
{
int arr[]={10, 3, 40, 20, 50, 80, 70};

int i = binSearch(arr,0,8,9,50);

if(i==1)
printf("found!!!\n");
else
  printf("not found!!!\n");



return 0;
}


int binSearch(int *arr,int low,int high,int length,int searchEle)
{
int mid=(low+high)/2;

if(low>high)
{
return 0;
}
else
{
if(arr[mid]==searchEle)
{
return 1;
}
else if(arr[mid-1]==searchEle)
{
return 1;
}
else if(arr[mid+1]==searchEle)
{
return 1;
}
else if(arr[mid]<searchEle)
{
return binSearch(arr,mid+1,high,length,searchEle);
}
else
{
return binSearch(arr,low,mid-1,length,searchEle);

}

}



}

let me know if I am wrong at some point !!! :)

Delete N nodes after M nodes of a linked list

Delete N nodes after M nodes of a linked list

Given a linked list and two integers M and N. Traverse the linked list such that you retain M nodes then delete next N nodes, continue the same till end of the linked list.
Difficulty Level: Rookie
Examples:

Input:
M = 2, N = 2
Linked List: 1->2->3->4->5->6->7->8
Output:
Linked List: 1->2->5->6

Input:
M = 3, N = 2
Linked List: 1->2->3->4->5->6->7->8->9->10
Output:
Linked List: 1->2->3->6->7->8

Input:
M = 1, N = 1
Linked List: 1->2->3->4->5->6->7->8->9->10
Output:
Linked List: 1->3->5->7->9

my sollution is ....

#include<stdio.h>

#include<stdlib.h>

struct node

{

int data;

struct node *link;

};

struct node *getNode()

{

struct node *p;

int data;

p=malloc(sizeof(struct node));

printf("enter the number\n");

scanf("%d",&data);

p->data=data;

p->link=NULL;

return p;

}

struct node *insertAtEnd(struct node *head)

{

struct node *newNode;

struct node *temp;

if(head==NULL)

{

newNode=getNode();

head=newNode;

}

else

{

temp=head;

while((temp->link)!=NULL)

{

temp=temp->link;

}

newNode=getNode();

temp->link=newNode;

}

return head;

}

void printList(struct node *head)

{

struct node *temp;

if(head==NULL)

{

printf("no element in the list\n");

}

else

{

temp=head;

while(temp!=NULL)

{

printf("--%d--",(temp->data));

temp=(temp->link);

}

printf("\n");

}

}

void delMN(struct node *head,int m ,int n)

{

int m1,n1;

struct node *ptr2,*ptr22;

m1=m-1;

n1=n-1;

struct node *ptr1=head;

while(1)

{

while(m1!=0)   // set ptr1 to the the location 

{

ptr1=ptr1->link;

if(ptr1==NULL) // to bring the control out of current while loop

{break;}

m1--;

}

if(ptr1==NULL) // to bring the contrlo out of main while loop.

{break;}

ptr2=ptr1->link;

(ptr1->link)=NULL;

while(n1!=0)

{

ptr22=ptr2;

ptr2=ptr2->link;

n1--;

free(ptr22);

if(ptr2==NULL)  // to bring the control out of current while loop 

{break;}

}

if(ptr2==NULL)   // to bring the control out of main while loop.

{break;}

// logic to delete the nodes and set the links to the appropriate node.

(ptr1->link)=(ptr2->link);

free(ptr2);

ptr1=ptr1->link;

if(ptr1==NULL)

{break;}

m1=m-1;

n1=n-1;

}

}

int main()

{

struct node *head;

head=NULL;

int ch,m,n;

while(1)

{

printf("\n1. insert at end \n2.delete \n3.printList \n4.exit\n");

scanf("%d",&ch);

switch(ch)

{

case 1: 

head=insertAtEnd(head);

break;

case 2: 

printf("value of m\n");

scanf("%d",&m);

printf("value of n\n");

scanf("%d",&n);

delMN(head,m,n);

break;

case 3:

printList(head);

break; 

  case 4:

exit(0);

break;

}

}

}

// Please let me know if any problem... :)