4.1. Searching in Arrays¶
- File:
SearchArray.ml
Let us put key-value arrays to some good use.
4.1.1. Linear Search¶
One of the most common operations with key-value arrays is searching, i.e., looking for the index of an element with some known key, or discovering that there is not such element in the array. The simplest implementation of searching walks through the entire array until the sought element is found, or the whole array is traversed:
let linear_search arr k =
let len = Array.length arr in
let res = ref None in
let i = ref 0 in
while !i < len && !res = None do
(if fst arr.(!i) = k
then res := Some ((!i, arr.(!i))));
i := !i + 1
done;
!res
We can now test it on a random array:
let a1 = [|(9, "lgora"); (0, "hvrxd"); (2, "zeuvd"); (2, "powdp"); (8, "sitgt");
(4, "khfnv"); (2, "omjkn"); (0, "txwyw"); (0, "wqwpu"); (0, "hwhju")|];;
# linear_search a1 4;;
- : (int * (int * string)) option = Some (5, (4, "khfnv"))
# linear_search a1 10;;
- : (int * (int * string)) option = None
In the first case, linear_search
has returned the index (5
) of
an element with the key 4, as well as the element itself. In the
second case, it returns None
, as there is no key 10
in the
array a1
.
4.1.2. Binary Search¶
Binary search is an efficient search procedure that works on a sorted array and looks for an element in it, repeatedly dividing its search-space by half:
let rec binary_search arr k =
let rec rank lo hi =
if hi <= lo
then
(* Empty array *)
None
(* Converged on a single element *)
else
let mid = lo + (hi - lo) / 2 in
if fst arr.(mid) = k
then Some (arr.(mid))
else if fst arr.(mid) < k
then rank (mid + 1) hi
else rank lo mid
in
rank 0 (Array.length arr)
The auxiliary procedure rank
keeps changing the search boundary by
recomputing the median of the search range and comparing the element
in it. This way it makes sure that the element is already found, or
the search space contains it if and only if the original array
contains it. Let us trace the binary search and figure out its
invariant:
let rec binary_search_print arr k =
let rec rank lo hi =
Printf.printf "Subarray: [";
let ls = array_to_list lo hi arr in
List.iter (fun (k, v) -> Printf.printf "(%d, %s); " k v) ls;
Printf.printf "]\n\n";
if hi <= lo
then
(* Empty array *)
None
(* Converged on a single element *)
else
let mid = lo + (hi - lo) / 2 in
if fst arr.(mid) = k
then Some (arr.(mid))
else if fst arr.(mid) < k
then rank (mid + 1) hi
else rank lo mid
in
rank 0 (Array.length arr)
let a2 = [|(0, "vzxtx"); (1, "hjqxi"); (3, "wzgsx"); (4, "hkuiu"); (4, "bvyjr");
(5, "hdgrv"); (5, "sobff"); (5, "bpelh"); (5, "xonjr"); (6, "qjzui");
(6, "syhze"); (8, "xyzxu"); (9, "gaixr"); (10, "obght"); (11, "wmiwb");
(11, "dzvmf"); (12, "teaum"); (13, "gazaf"); (14, "svemi"); (15, "rxpus");
(15, "agajq"); (21, "vztoj"); (21, "oszgf"); (21, "ylxiy"); (23, "itosu");
(26, "nondm"); (27, "yazoj"); (28, "nqzcl"); (29, "lfevj"); (31, "hfcds");
(31, "pgrym"); (32, "yghgg")|];;
Now, as a2
is sorted, we can run the binary search on it:
# binary_search_print a2 32;;
Subarray: [(0, vzxtx); (1, hjqxi); (3, wzgsx); (4, hkuiu); (4, bvyjr); (5, hdgrv); (5, sobff); (5, bpelh); (5, xonjr); (6, qjzui); (6, syhze); (8, xyzxu); (9, gaixr); (10, obght); (11, wmiwb); (11, dzvmf); (12, teaum); (13, gazaf); (14, svemi); (15, rxpus); (15, agajq); (21, vztoj); (21, oszgf); (21, ylxiy); (23, itosu); (26, nondm); (27, yazoj); (28, nqzcl); (29, lfevj); (31, hfcds); (31, pgrym); (32, yghgg); ]
Subarray: [(13, gazaf); (14, svemi); (15, rxpus); (15, agajq); (21, vztoj); (21, oszgf); (21, ylxiy); (23, itosu); (26, nondm); (27, yazoj); (28, nqzcl); (29, lfevj); (31, hfcds); (31, pgrym); (32, yghgg); ]
Subarray: [(26, nondm); (27, yazoj); (28, nqzcl); (29, lfevj); (31, hfcds); (31, pgrym); (32, yghgg); ]
Subarray: [(31, hfcds); (31, pgrym); (32, yghgg); ]
Subarray: [(32, yghgg); ]
- : (int * string) option = Some (32, "yghgg")
Notice that at each iteration the sub-array halves, so binary_sort
does not even have consider the entire array, and this is the crux of
its efficiency!
4.1.3. Binary Search Invariant¶
Binary search crucially relies on the fact that the given array (and
hence its contiguous sub-array segments) are sorted, so, upon
comparing the key to the middle, it can safely ignore the half that is
irrelevant for it. This can be captured by the following precondition
we are going to give to rank
. It postulates that a sought element
with a key k
is in the whole array if and only if it is in the
sub-array bound by lo .. hi
, which we are about to consider:
let binary_search_rank_pre arr lo hi k =
let len = Array.length arr in
let ls = array_to_list 0 len arr in
let ls' = array_to_list lo hi arr in
if List.exists (fun e -> fst e = k) ls
then List.exists (fun e -> fst e = k) ls'
else not (List.exists (fun e -> fst e = k) ls')
We can also annotate our implementation with this invariant and test it:
let binary_search_inv arr k =
let rec rank lo hi =
Printf.printf "lo = %d, hi = %d\n" lo hi;
Printf.printf "Subarray: [";
let ls = array_to_list lo hi arr in
List.iter (fun (k, v) -> Printf.printf "(%d, %s); " k v) ls;
Printf.printf "]\n";
if hi <= lo
then
(* Empty array *)
None
(* Converged on a single element *)
else
let mid = lo + (hi - lo) / 2 in
Printf.printf "mid = %d\n" mid;
if fst arr.(mid) = k
then Some (arr.(mid))
else if fst arr.(mid) < k
then
(Printf.printf "THEN: lo = %d, hi = %d\n\n" (mid + 1) hi;
assert (binary_search_rank_pre arr (mid + 1) hi k);
rank (mid + 1) hi)
else
(Printf.printf "ELSE: lo = %d, hi = %d\n\n" lo mid;
assert (binary_search_rank_pre arr lo mid k);
rank lo mid)
in
let len = Array.length arr in
assert (binary_search_rank_pre arr 0 len k);
rank 0 len
4.1.4. The Main Idea of Divide-and-Conquer algorithms¶
The binary search algorithm is an example of the so-called divide-and-conquer approach. In this approach the processing of a data (a key-value array in our case) is based on multi-branched recursion. A divide-and-conquer algorithm works by recursively breaking down a problem into two or more sub-problems of the same or related type, until those become simple enough to be solved directly (such as reporting an element in a single-element sub-array). The solutions to the sub-problems are then combined to give a solution to the original problem.
Checkpoint question: What is the “divide” and what is a “conquer” phase of the binary search?