assignment_02.cpp (3729B)
1 /* Program to search an element from a list using Linear Search or Binary Search */ 2 3 #include <iostream> 4 #include <iomanip> 5 6 using namespace std; 7 8 typedef struct MenuItem { 9 int id; 10 const char* name; 11 } menu; 12 13 class SearchList { 14 private: 15 int *arr; 16 int n; 17 18 void insertionSort() { 19 for (int i = 1; i < n; i++) { 20 int key = arr[i]; 21 int j = i - 1; 22 while (j >= 0 && arr[j] > key) { 23 arr[j + 1] = arr[j]; 24 j--; 25 } 26 arr[j + 1] = key; 27 } 28 } 29 30 public: 31 SearchList(int size) { 32 n = size; 33 arr = new int[n]; 34 } 35 36 void inputElements() { 37 cout << "\nEnter " << n << " elements: "; 38 for (int i = 0; i < n; i++) { 39 cin >> arr[i]; 40 } 41 } 42 43 int linearSearch(int key) { 44 for (int i = 0; i < n; i++) { 45 if (arr[i] == key) { 46 return i; 47 } 48 } 49 return -1; 50 } 51 52 int binarySearch(int key) { 53 // Binary search requires the collection to be sorted 54 insertionSort(); 55 cout << "\n(Array automatically sorted for Binary Search)"; 56 display(); 57 58 int left = 0; 59 int right = n - 1; 60 61 while (left <= right) { 62 int mid = left + (right - left) / 2; 63 64 if (arr[mid] == key) { 65 return mid; 66 } else if (arr[mid] < key) { 67 left = mid + 1; 68 } else { 69 right = mid - 1; 70 } 71 } 72 return -1; 73 } 74 75 void display() { 76 cout << "\nCurrent List: "; 77 for (int i = 0; i < n; i++) { 78 cout << arr[i] << " "; 79 } 80 cout << endl; 81 } 82 83 void printMenu() { 84 menu items[] = { 85 {1, "Linear Search"}, {2, "Binary Search"}, 86 {0, "Display List"}, {-1, "Exit"} 87 }; 88 89 cout << "\n## Choose Search Method --\n--------------------------------------------\n"; 90 for (int i = 0; i < 4; i++) { 91 cout << items[i].id << ". " << left << setw(20) << items[i].name; 92 if (i % 2 == 1) cout << "\n"; 93 } 94 } 95 96 ~SearchList() { 97 delete[] arr; 98 } 99 }; 100 101 int main() { 102 int n, choice, key; 103 cout << "Enter the size of the list: "; 104 cin >> n; 105 106 if (n <= 0) { 107 cout << "Invalid list size!\n"; 108 return 0; 109 } 110 111 SearchList list(n); 112 list.inputElements(); 113 114 while (true) { 115 list.printMenu(); 116 cout << "Enter your choice: "; 117 cin >> choice; 118 119 switch (choice) { 120 case 1: { 121 cout << "\nEnter element to search: "; 122 cin >> key; 123 int index = list.linearSearch(key); 124 if (index != -1) 125 cout << "\nElement " << key << " found at index " << index << ".\n"; 126 else 127 cout << "\nElement " << key << " not found in the list.\n"; 128 break; 129 } 130 case 2: { 131 cout << "\nEnter element to search: "; 132 cin >> key; 133 int index = list.binarySearch(key); 134 if (index != -1) 135 cout << "\nElement " << key << " found at index " << index << " in sorted array.\n"; 136 else 137 cout << "\nElement " << key << " not found in the list.\n"; 138 break; 139 } 140 case 0: 141 list.display(); 142 break; 143 case -1: 144 cout << "\nExiting program.....\nMemory cleared!\nExit 0\n"; 145 return 0; 146 default: 147 cout << "\nEntered wrong choice. Try again.\n"; 148 } 149 } 150 }