100% programmers, during training, sooner or later face the need to check for certain values in an array. There are several well-known search algorithms in programming languages. Now we look at the simplest of them (but not the most effective) – linear search or sequential search. Due to the fact, that search is conducted through the full brute force elements in the array and compare its value with the specified key, the algorithm is quite low speed.
To tell there is nothing special – It is better to show a linear search to work. In the example below to declare an array 50 elements and fill it using random number generator rand(). Prompt the user to enter the desired value with the keyboard and implement check for this value in our array. If a value is found in any element of the array – We display the index of the element. This is a classic example . It is hard and come up with something better to demonstrate the linear search in C ++.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 | #include <iostream> #include <iomanip> #include <ctime> using namespace std; //прототипы функций int linSearch(int arr[], int requiredKey, int size); // линейный поиск void showArr(int arr[], int size); // показ массива int main() { setlocale(LC_ALL, "rus"); const int arrSize = 50; int arr[arrSize]; int requiredKey = 0; // искомое значение (ключ) int nElement = 0; // номер элемента массива srand(time(NULL)); //запись случ. чисел в массив от 1 до 50 for (int i = 0; i < arrSize; i++) { arr[i] = 1 + rand() % 50; } showArr(arr, arrSize); cout << "Какое число необходимо искать? "; cin >> requiredKey; // ввод искомого числа //поиск искомого числа и запись номера элемента nElement = linSearch(arr, requiredKey, arrSize); if (nElement != -1) { //если в массиве найдено искомое число - выводим индекс элемента на экран cout << "Значение " << requiredKey << " находится в ячейке с индексом: " << nElement << endl; } else { //если в массиве не найдено искомое число cout << "В массиве нет такого значения" << endl; } return 0; } //вывод массива на экран void showArr(int arr[], int arrSize) { for (int i = 0; i < arrSize; i++) { cout << setw(4) << arr[i]; if ((i + 1) % 10 == 0) { cout << endl; } } cout << endl << endl; } //линейный поиск int linSearch(int arr[], int requiredKey, int arrSize) { for (int i = 0; i < arrSize; i++) { if (arr[i] == requiredKey) return i; } return -1; } |
Function performs a linear search is defined in strings 62-70. She returns to the program -1 in that case, if the value, is looking for a user, will not be found in the array. If the value is found – function returns the array index, wherein the value is stored.
Run:
In the absence of values in an array:
After looking at the first picture, you will immediately notice, that in a cell with index 6 the desired value is found and the program shuts down, although the cells 23 and 33 it array are the same values. If you're okay with that, the index of the first element and is the result of the work program. Otherwise, the program should be finished, to find and record (for example, in a single array) all indices of cells, store the desired number (key).
Typically, a linear search is used to search in a small single array, that is not sorted. In other cases,, better and more efficient first sort the array and to use other search algorithms. For example binary (binary) Search or other.
Function, checking the presence of the element in the array should return bool (true if the element is false, and if it is not).
There is no sense to return the value of the element, tk. client (Togo, who caused function) already have this value – because he gave it as the second argument, Why should he get it back?
To return -1 in the absence of the element even more pointless, Imagine that I want to check for values -1 array.
He looked attentively, I confess ) – function does not return a value, and the index, therefore there are no problems, all right )