The binary search algorithm in the textbook (page 443) may be used to search an

Question

The binary search algorithm in the textbook (page 443) may be used to search an array when the elements are in order. This algorithm is analogous to the following approach for finding a name in a telephone book.

a. Open the book in the middle, and look at the middle name on the page.
b. If the name isn't the one you're looking for, decide whether it comes before or after the name you want.
c. Take the appropriate half of the section of the book you were looking in and repeat these steps until you land on the name.

Hint: think of binary search using an interval (two index values: begin and end). On each iteration, the span of the interval should be divided in half. To do this, update begin and end as appropriate. When you start the binary search, the begin is 0 and the end is the index of the last element of the array (i.e., length - 1). Let index = (begin + end) / 2. Examine the array element at index. If that array element is smaller than what you're searching for, then set end to index-1; otherwise, if the array element was larger, then set begin to index+1. Obviously, if the array element is what you're searching for, you're done searching!

Explanation / Answer

please rate - thanks

#include <stdio.h>
#include <conio.h>
int bsearch(int[],int,int);
int main()
{int numbers[]={8,9,12,34,56,66,76,89},key,index,arraylength=8;
printf("Enter number to search: ");
scanf("%d",&key);
index=bsearch(numbers,key,arraylength);
if(index<0)
     printf("%d not found ",key);
else
     printf("%d found at index %d ",key,index);
getch();
return 0;
}
int bsearch(int id[],int key,int max)
{int mid,low=0;
max--;
while(low<=max )
    {mid=(low+max)/2;
    if(id[mid]<key)
       low = mid + 1;
    else
        {if( id[ mid ]>key )
            max = mid - 1;                   
        else
           {
           return mid;
           }
        }
     }

return -1;
}

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.