Searching
In this case, the problem we are trying to solve with search is: given an element N - find that element in a sorted array. The only algorithm worth mentioning here is the binary search.
Binary Search
- Runtime: O(log N)
- Recommended reading
As we know that the array is sorted, we can use a divide and conquer approach. Here we will repeatedly divide the array by using the middle point as a pivot. If the element we are after is smaller than this pivot, we will look only to the left-hand side of the array, and start this process all over again.
By doing this we would reduce the runtime to O(log N), rather than doing a linear search - which would take O(N).
Here is the code in Java:
Recursive approach
int binarySearch(int[] array, int n, int low, int high) {
if (low > high) return -1;
int middle = (low + high) / 2;
int pivot = array[middle];
if (pivot < n) return binarySearch(array, n, middle + 1, high); // need to go right
else if (pivot > n) return binarySearch(array, n, low, middle - 1); // need to go left
else return pivot;
}
Iterative approach
int binarySearchIterative(int[] array, int n) {
int low = 0;
int high = array.length - 1;
int mid, pivot;
while (low <= high) {
mid = (low + high) / 2;
pivot = array[mid];
if (pivot < n) low = mid + 1;
else if (pivot > n) high = mid - 1;
else return pivot;
}
return -1; // Error
}