Code:
a) Open the book in the middle, and look at the middle name on the page.
b) If the middle name isn’t the one you are looking for, decide wither it comes before orafter the name you want.
Take the appropriate half of the section of the book you were looking in and repeat thesesteps until you land on the name you want. Algorithm for Binary Search
- Let bottom be the subscript of the initial array element.
- Let top be the subscript of the last array element.
- Let found be false.
- Repeat as long as bottom isn’t greater than top and the target has not been found.
- (a) Let middle be the subscript of the element halfway between bottom and top.
- (b) If the element at middle is the targetSet found to true and index to middle.
- (c) Else if the element at middle is larger than targetLet top be middle - 1
- (d) Else Let bottom be middle + 1.
- In the main function declare the following array:int my numbers[] = {
2430,4719,2247,1397, 155,2401,3015,2324, 670,2134,469, 952,3881,3633,3459,4366, 19, 935,1610, 724,4373,2111,4542,1596,4244,4822,4964,1504, 462, 652,1561,4557,4791, 387, 522 ,513,4872,4569, 241,2662,3241,2475,3664,4028,2064,3993, 572, 649, 418,3283,4347,3207,3349, 100,3651,4194,4725,1276,1244, 722,2019,1232,3491, 606, 261,2054,3699,3901,1471,4477,1569, 438,1439,3028,1839,1692,1209,4500,4996,1097,3565,3068,2911,4416, 579,3994,1291,2914,3728,1023,868,3652,3458,1461,4763,3904,1822,4594, 900,1763,1645,1933,4541, 517,2676,4744,1292,4498,3848,3508,2425, 87,2627,2532,2375,3623,3112,932,1368, 501};
- Sort my numbers array using the sort function you implemented in Question 2
- Ask the user to enter the number he is looking for, call the binary search function todetermine if the number is in the array and the number of searches the function tookto locate or to determine that the number is not found. Repeat as long as the userentered a positive number.
int binarySearch(int arr[], int value, int left, int right);
int main(void){
int value;
int my_numbers[] = {
2430,4719,2247,1397, 155,2401,3015,2324, 670,2134, 469, 952,3881,3633,3459,4366, 19, 935,1610, 724,
4373,2111,4542,1596,4244,4822,4964,1504, 462, 652, 1561,4557,4791, 387, 522 ,513,4872,4569, 241,2662,
3241,2475,3664,4028,2064,3993, 572, 649, 418,3283, 4347,3207,3349, 100,3651,4194,4725,1276,1244, 722,
2019,1232,3491, 606, 261,2054,3699,3901,1471,4477, 1569, 438,1439,3028,1839,1692,1209,4500,4996,1097,
3565,3068,2911,4416, 579,3994,1291,2914,3728,1023, 868,3652,3458,1461,4763,3904,1822,4594, 900,1763,
1645,1933,4541, 517,2676,4744,1292,4498,3848,3508, 2425, 87,2627,2532,2375,3623,3112,932,1368, 501};
printf("What value are you seeking enter a negative number to exit?");
scanf("%d",&value);
binarySearch(&value);
return(0);
}
int binarySearch(int arr[], int value, int left, int right) { // Here we declare left, right, as parameters
while (left <= right) {
int middle = (left + right) / 2; //Calculates middle using integer division
//Middle is declared as an int variable here
//Let's look at how this works in the code
if (arr[middle] == value) // If we found our target value at middle, we can return that index
//We reach this part of the code :)
return middle;
else if (arr[middle] > value) //If middle is greater than the target, ignore the right half
right = middle - 1;
else
// Now this is our case in the example
//Since the middle is less than the target, we can go ahead and
//look again starting at the next value in the array and looking to the right
left = middle + 1;
}
return -1;
}