Searching

Претърсване чрез обхождане §

Time complexity:

Обхожда се целия масив и се търси елемента.

bool search_all(const int *arr, unsigned n, int x) {  
    bool isFound = false;  
    for (int i = 0; i < n; ++i) {  
        if (x == arr[i]) {  
            isFound = true;  
        }  
    }  
    return isFound;  
}

“Докато намериш с ‘котва’” §

Търси се, докато елемента не се намери, като преди това търсения елемент се добавя в края на масива.

bool search_until(int *arr, unsigned n, int x) {  
    arr[n] = x;  
  
    int i = 0;  
  
	while (arr[i] != x) {
	    i++;  
	}  
  
    return i < n;  
}

Дихотомично търсене §

binary search

bool binary_search(const int *arr, unsigned n, int x) {  
    int l = 0;  
    int r = n - 1;  
  
    while (r >= l) {  
        unsigned m = l + (r - l) / 2;  
  
        if (arr[m] == x) {  
            return true;  
        } else {  
            if (arr[m] < x) {  
                l = m + 1;  
            } else {  
                r = m - 1;  
            }  
        }  
    }  
  
    return false;  
}