bin_search_in_DLL.c

int binary_search_DLL()
{
    sorting();  //  'cause binary search is possible in sorted list only
    int search_key;
    printf("\n\nEnter the element : "); //  user promt for
	scanf("%d",&search_key);    //  searching element

    struct node *ptr, *lptr, *rptr, *midptr;
    
    lptr = header;  //  left end of the working list, initially header
    rptr = tailor;  //  left end of the working list, initially tailer
    
    int num_nodes = count;  //  total no. of nodes
    int pos = -1;   //  position of the searched node stored here
    int mid_pos = 0, lpos = 0, rpos = count-1;//  position of the mid element and the left-most element

    while(lpos <= rpos && lpos <= count && rpos <= count && rpos >= 0 && lpos >= 0) //  all bounds conditions
    {
        ptr = lptr; //  start from the leftmost node
        int i;
        
        for(i=0; i<num_nodes/2; i++)    //  iterate to the middle node
            ptr=ptr->rlink;
        midptr = ptr;   //  the middle node
        mid_pos = lpos + i; //  the middle position
        
        // printf("%d, i=%d\n", midptr->data, mid_pos); //  ignore: used for print-debugging

        if(midptr->data == search_key){ //  if the searching element is the middle element
            pos = mid_pos;  //  found in mid_pos, set that to pos
            break; 
        }
            
        else if(midptr->data < search_key){
            lptr = midptr->rlink;   //  shifting the leftmost node (changing the working list bounds)
            lpos = mid_pos + 1;     //  shifting the leftmost position
            num_nodes = rpos - mid_pos;       //  the new working list has reduced no of nodes (by half)
        }
            
        else if(midptr->data > search_key){
            rptr = midptr->llink;  //  the rightmost pointer is shifted (changing the working list bounds)
            rpos = mid_pos-1;       //  shifting the rightmost position
            num_nodes = rpos - mid_pos;
        }
    }

    if(pos == -1)   //  if value of pos is unaltered: see declaration of pos
        printf("\n%d is not found",search_key);
    else    //  bravo! found it
    printf("\n%d is found at %d",search_key, pos+1);    //  'cause pos was 0-indexed
}