Java Project: Search Algorithms Comparison

Searching is one of the most important function coded by programmers for various needs. There are several searching algorithms, but we will focus in this project on Linear/Sequential and Binary Search algorithms.

? Linear Search refers to the method where the key is checked against the list elements one at a time in sequential order until it is found or the list is exhausted. For instance, given the key = 128, and the list provided below, the linear search requires 9 checks before the match is found.

Linear search doesnt require the list be ordered in a particular way. In this project, the list is based on a single dimensional integer array.

? Binary Search is very different from Linear Search. It requires that the list is sorted before any search is performed. At each iteration, three checks are performed.

a. If the key matches the mid element in the list, the search is terminated.

b. If the key is greater than the mid value, the lower half of the list is ignored.

c. If the key is smaller than the mid value, the upper half of the list is ignored.

The purpose of this project is to compare the two searching algorithms and assess which one would perform better.

1) You are provided two input files (key.txt and data.txt) that are generated using the code provided along with this project. The file key.txt consists of search values while data.txt the repository on which the search is performed.

2) The list should be organized as an integer array using input file data.txt. Please note that for the binary search, the list must be sorted first before any search operation. The search keys should be stored in an integer array using the input key.txt.

3) The comparison is done by timing each search for both the linear and binary search algorithm. The code sample provided with this project shows how to use Java timer to measure elapsed time. To be consistent, please use millisecond

4) The comparison report should be displayed on the standard output device as well as printed into an output file called comparison_report.txt. The report should show the list of the keys and the time it took to find a match or not.

General Requirements

- Use NetBeans, that would be OK for Java only

- The input file is provided to you along with this assignment and you must use that.

- The code must be documented and formatted consistently. Please follow the Java Coding Convention given below.

data.txt

237 215 982 641 125 602 284 853 226 274

875 362 608 128 299 142 135 729 923 725

334 635 310 573 834 6 689 646 375 20

180 588 350 374 367 11 924 669 44 701

955 498 202 418 913 818 258 293 150 658

690 991 884 931 270 435 599 809 599 525

779 158 228 767 853 182 269 858 450 126

510 733 35 918 752 165 306 712 291 650

990 997 608 953 659 699 532 955 549 156

686 985 554 717 465 794 31 713 12 164

83 98 783 594 992 524 1 224 119 398

764 576 99 261 170 423 638 863 329 274

360 537 89 487 695 254 431 369 64 988

34 51 906 628 138 8 75 510 256 677

597 607 721 204 208 336 172 30 675 340

19 947 765 141 62 57 590 540 978 807

835 211 521 901 733 73 467 698 483 921

515 458 790 167 860 962 506 97 650 384

37 453 885 772 384 629 87 253 930 123

119 697 620 75 46 445 567 356 855 413

145 546 708 401 351 803 659 5 837 771

255 219 712 15 347 990 988 963 121 774

65 352 673 811 72 734 901 575 20 969

465 285 740 723 168 56 789 718 113 282

35 772 360 962 280 637 41 512 358 772

736 40 390 94 820 472 139 960 778 376

520 765 677 13 382 481 891 122 970 28

682 444 243 430 122 744 377 411 708 324

865 60 848 239 885 570 637 589 984 799

560 330 415 619 887 850 371 344 608 219

515 682 747 209 295 334 806 500 727 414

359 511 353 927 164 95 930 231 886 566

604 214 404 291 573 240 500 872 496 227

420 344 773 820 79 394 739 328 675 135

638 338 903 356 452 624 881 532 209 106

909 214 218 129 522 438 526 663 823 66

273 248 531 835 754 436 10 526 44 521

939 742 82 129 582 920 11 749 731 283

878 22 302 266 823 219 422 183 814 724

325 45 337 562 137 626 360 616 729 463

782 194 516 942 519 577 930 239 149 121

110 927 429 223 803 645 278 689 740 362

521 572 792 701 940 284 234 280 433 180

454 426 428 378 264 314 841 198 54 588

763 207 318 171 634 402 866 452 628 560

175 355 604 266 686 781 191 36 113 145

123 659 671 571 714 780 19 853 60 251

863 652 492 772 526 493 57 10 542 835

236 474 428 511 817 363 506 690 990 396

76 185 648 169 720 901 949 860 243 277

765 692 328 475 250 941 395 329 662 916

644 390 283 428 887 440 845 530 352 575

876 617 757 444 22 667 627 677 609 29

738 238 78 30 149 20 913 908 345 497

101 59 871 152 244 370 612 12 212 851

853 697 350 23 392 894 303 508 694 214

881 397 877 554 388 60 402 36 774 590

547 587 858 675 267 542 620 368 718 582

154 515 932 900 975 778 51 988 385 801

388 829 18 286 544 542 707 83 828 711

356 215 39 585 665 409 348 123 183 354

227 218 516 541 129 956 547 582 432 113

903 373 234 822 175 430 583 655 24 830

510 929 432 739 607 513 774 936 151 668

568 268 381 980 68 838 41 844 992 199

540 217 565 868 995 12 341 807 557 496

933 521 900 76 214 670 280 838 798 52

894 573 291 1 600 489 151 649 199 889

431 153 907 648 718 163 979 261 527 862

295 517 152 97 178 807 97 364 406 612

163 938 384 225 517 983 610 603 626 682

495 254 823 496 633 442 40 925 878 130

810 143 113 146 659 113 661 236 766 616

388 895 378 110 614 190 234 152 677 520

255 278 493 648 986 375 753 419 406 311

953 354 577 598 527 411 483 869 784 152

72 248 792 860 672 251 766 989 381 338

903 499 404 905 246 203 324 692 113 24

68 380 694 31 33 367 813 533 765 554

655 127 995 166 212 237 31 861 755 245

723 431 210 360 163 453 165 747 114 17

339 27 998 960 20 221 502 342 646 714

643 564 959 356 604 71 389 672 916 544

169 872 263 388 274 795 978 104 694 363

663 363 323 626 608 640 700 146 43 686

775 848 595 654 187 628 95 456 751 376

540 929 765 930 998 901 325 208 275 934

742 823 448 47 863 696 45 431 788 256

220 901 348 530 296 636 743 315 663 483

957 81 297 356 50 185 563 894 469 372

780 610 559 589 121 103 505 793 331 338

111 564 422 901 753 636 653 186 391 732

865 517 748 663 881 252 20 959 275 467

191 609 128 368 919 455 845 616 798 666

789 652 705 361 685 756 225 690 704 197

688 284 920 418 568 175 542 685 687 817

417 352 135 93 682 373 314 474 504 726

98 213 247 97 542 380 180 84 561 73

803 257 573 678 393 414 253 955 278 140

464 370 754 833 649 723 728 172 634 337

key.txt

72 365 593 848 422 278 731 753 799 946

653 203 388 769 778 112 760 109 87 41

4 1 2 7 256 1024 128 24