Hi! I need the program for C programming lab #8 "Binary search, Arrays"

the header file is included

CS 1057 C Programming - Spring 2017

Purpose:

use arrays to sort and search through data.

implement the selection sort as written in the textbook.

calculate the size of a provided array dynamically, at run time, as shown in class.

write your program in such a way that it could be used with ANY set of data.

use top-down design in your code. Have only function invocations in your main() function.

Prerequisites:

Review through Chapter 7 in the textbook (Problem Solving and Program Design in C, 8th Edition by Hanly & Koffman) before attempting this lab.

Problem Specification:

Implement a binary search, an algorithm that requires the array to be searched to be sorted. Details are on page 452 of the textbook, problem #12.

The selection sort code can be found on page 407. Searching for 76 Your program should begin with the following prompt, using the symbolic constant of your name provided in the program header file, lab8.h: MERGE ARRAYS PROGRAM WRITTEN IN C This program was written by Dan Data. 15 values in the array.

What value are you seeking? Page 2 of 3 Tasks: When the user enters a number, return the following information (NOTE: this is just sample output): What value are you seeking?

76 The value 76 was found in the list of numbers. It took 4 searches to locate that number in the sorted array.

Then your program should prompt the user again. If the number is not found, indicate that it wasnt in the array, and say how many searches it took to determine it wasnt in there, and indicate the numbers in the array that are nearest to the value being searched for. What value are you seeking?

79 The value 79 was NOT found in the list of numbers.

It took 5 searches to determine that number is not in the sorted array.

The closest numbers to it are 77 and 82.

Create a header file with the data for the array to search already in it.

Heres the data you can use:

#ifndef MY_NUMBERS

#define MY_NUMBERS

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,

};

#endif

Ive put the data up on github, so you can download the header file with the command git clone

https://github.com/untamedspud/numbers-spring2017.git

BOOK : Problem Solving and Program Design in C, 8th Edition by Hanly & Koffman

12. The binary search algorithm that follows 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 middle name isnt the one youre looking for, decide whether it comes before or after the name you want. 450 Chapter 7 Arrays

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. ALGORITHM FOR BINARY SEARCH

1. Let bottom be the subscript of the initial array element.

2. Let top be the subscript of the last array element.

3. Let found be false.

4. Repeat as long as bottom isnt greater than top and the target has not been found

5. Let middle be the subscript of the element halfway between bottom and top.

6. if the element at middle is the target

7. Set found to true and index to middle. else if the element at middle is larger than the target

8. Let top be middle 1. else

9. Let bottom be middle + 1. Write and test a function binary_srch that implements this algorithm for an array of integers. When there is a large number of array elements, which function do you think is faster: binary_srch or the linear search function of Fig. 7.14 ?