Pure Programmer
Project: Binary Search
You can easily and efficiently search through an array of values if they are ordered by using a [[Binary_search_algorithm|Binary Search]]. The idea is to check the middle value and determine if the search value is below or above that point. Either way you can eliminate half the possiblities with one check. Then repeat this procedure with the remaining values, eliminating half with each check until you find the value you are looking for. If N is the number of items in the array, you should be able to find the desired value with log₂N comparisons which is very fast.
Write a function that performs a Binary Search on a list for a specified value. Your main program should fills a list of integers with random values then perform various test searches on the list. Be sure to handle the edge cases where the search value is less than the first value, greater than the last value or if the value is not in the list at all.
Time how long it takes to generate N random integers, sort those N integers and search for those integers N times. Do this for N = 10³, 10⁴, 10⁵, 10⁶ and 10⁷. Then plot the results. Do the curves for generating, sorting and searching have different shapes?
The shape of these curves that describe the behavior of an algorithm as N gets larger are referred to using [[Big O notation]]. Typically algorithms are classified by Big O notations such as `O(1)`, `O(log x)`, `O(x)`, `O(x log x)`, `O(x^2)` or `O(x^3)`. These notations are listed in order of increasingly larger growth as N increases. If we had the choice to choose between two algorithms of `O(log x)` or `O(x)`, we would generally prefer the `O(log x)` since its execution time complexity grows more slowly then does `O(x)`. The most desireable is `O(1)` which is constant time. No matter the size of N, it always takes the same amount of time.
See Quicksort for a sort algorithm you can use for a sort function and LCGPseudorandomGenerator for a random number generator function.
Output
$ rustc BinarySearch.rs
error: unknown format trait `d`
--> BinarySearch.rs:85:39
|
85 | println!("{}", format!("Duration: {0:d} ms", stop - start));
| ^
|
= note: the only appropriate formatting traits are:
- ``, which uses the `Display` trait
- `?`, which uses the `Debug` trait
- `e`, which uses the `LowerExp` trait
- `E`, which uses the `UpperExp` trait
- `o`, which uses the `Octal` trait
- `p`, which uses the `Pointer` trait
- `b`, which uses the `Binary` trait
- `x`, which uses the `LowerHex` trait
- `X`, which uses the `UpperHex` trait
error: unknown format trait `d`
--> BinarySearch.rs:91:39
|
91 | println!("{}", format!("Duration: {0:d} ms", stop - start));
| ^
|
= note: the only appropriate formatting traits are:
- ``, which uses the `Display` trait
- `?`, which uses the `Debug` trait
- `e`, which uses the `LowerExp` trait
- `E`, which uses the `UpperExp` trait
- `o`, which uses the `Octal` trait
- `p`, which uses the `Pointer` trait
- `b`, which uses the `Binary` trait
- `x`, which uses the `LowerHex` trait
- `X`, which uses the `UpperHex` trait
error: unknown format trait `d`
--> BinarySearch.rs:104:39
|
104 | println!("{}", format!("Duration: {0:d} ms", stop - start));
| ^
|
= note: the only appropriate formatting traits are:
- ``, which uses the `Display` trait
- `?`, which uses the `Debug` trait
- `e`, which uses the `LowerExp` trait
- `E`, which uses the `UpperExp` trait
- `o`, which uses the `Octal` trait
- `p`, which uses the `Pointer` trait
- `b`, which uses the `Binary` trait
- `x`, which uses the `LowerHex` trait
- `X`, which uses the `UpperHex` trait
error[E0425]: cannot find function `exit` in this scope
--> BinarySearch.rs:70:3
|
70 | exit(1);
| ^^^^ not found in this scope
|
help: consider importing this function
|
8 + use std::process::exit;
|
error[E0425]: cannot find value `Utils` in this scope
--> BinarySearch.rs:72:29
|
72 | let mut sampleSize:isize = Utils.stoiWithDefault(args[1], 10);
| ^^^^^ not found in this scope
warning: denote infinite loops with `loop { ... }`
--> BinarySearch.rs:30:2
|
30 | while true {
| ^^^^^^^^^^ help: use `loop`
|
= note: `#[warn(while_true)]` on by default
error[E0308]: mismatched types
--> BinarySearch.rs:12:24
|
12 | let mut right:isize = list.len() - 1;
| ----- ^^^^^^^^^^^^^^ expected `isize`, found `usize`
| |
| expected due to this
|
help: you can convert a `usize` to an `isize` and panic if the converted value doesn't fit
|
12 | let mut right:isize = (list.len() - 1).try_into().unwrap();
| + +++++++++++++++++++++
error[E0277]: the type `[isize]` cannot be indexed by `isize`
--> BinarySearch.rs:15:11
|
15 | if list[m] < value {
| ^ slice indices are of type `usize` or ranges of `usize`
|
= help: the trait `SliceIndex<[isize]>` is not implemented for `isize`
= help: the trait `SliceIndex<[T]>` is implemented for `usize`
= note: required for `Vec<isize>` to implement `Index<isize>`
error[E0277]: the type `[isize]` cannot be indexed by `isize`
--> BinarySearch.rs:17:18
|
17 | } else if list[m] > value {
| ^ slice indices are of type `usize` or ranges of `usize`
|
= help: the trait `SliceIndex<[isize]>` is not implemented for `isize`
= help: the trait `SliceIndex<[T]>` is implemented for `usize`
= note: required for `Vec<isize>` to implement `Index<isize>`
error[E0277]: the type `[isize]` cannot be indexed by `isize`
--> BinarySearch.rs:27:25
|
27 | let pivot:isize = list[(high + low) / 2];
| ^^^^^^^^^^^^^^^^ slice indices are of type `usize` or ranges of `usize`
|
= help: the trait `SliceIndex<[isize]>` is not implemented for `isize`
= help: the trait `SliceIndex<[T]>` is implemented for `usize`
= note: required for `Vec<isize>` to implement `Index<isize>`
error[E0277]: the type `[isize]` cannot be indexed by `isize`
--> BinarySearch.rs:33:14
|
33 | if !(list[i] < pivot) { break; }
| ^ slice indices are of type `usize` or ranges of `usize`
|
= help: the trait `SliceIndex<[isize]>` is not implemented for `isize`
= help: the trait `SliceIndex<[T]>` is implemented for `usize`
= note: required for `Vec<isize>` to implement `Index<isize>`
error[E0277]: the type `[isize]` cannot be indexed by `isize`
--> BinarySearch.rs:37:14
|
37 | if !(list[j] > pivot) { break; }
| ^ slice indices are of type `usize` or ranges of `usize`
|
= help: the trait `SliceIndex<[isize]>` is not implemented for `isize`
= help: the trait `SliceIndex<[T]>` is implemented for `usize`
= note: required for `Vec<isize>` to implement `Index<isize>`
error[E0277]: the type `[isize]` cannot be indexed by `isize`
--> BinarySearch.rs:42:25
|
42 | let temp:isize = list[j];
| ^ slice indices are of type `usize` or ranges of `usize`
|
= help: the trait `SliceIndex<[isize]>` is not implemented for `isize`
= help: the trait `SliceIndex<[T]>` is implemented for `usize`
= note: required for `Vec<isize>` to implement `Index<isize>`
error[E0277]: the type `[isize]` cannot be indexed by `isize`
--> BinarySearch.rs:43:8
|
43 | list[j] = list[i];
| ^ slice indices are of type `usize` or ranges of `usize`
|
= help: the trait `SliceIndex<[isize]>` is not implemented for `isize`
= help: the trait `SliceIndex<[T]>` is implemented for `usize`
= note: required for `Vec<isize>` to implement `Index<isize>`
error[E0277]: the type `[isize]` cannot be indexed by `isize`
--> BinarySearch.rs:43:18
|
43 | list[j] = list[i];
| ^ slice indices are of type `usize` or ranges of `usize`
|
= help: the trait `SliceIndex<[isize]>` is not implemented for `isize`
= help: the trait `SliceIndex<[T]>` is implemented for `usize`
= note: required for `Vec<isize>` to implement `Index<isize>`
error[E0277]: the type `[isize]` cannot be indexed by `isize`
--> BinarySearch.rs:44:8
|
44 | list[i] = temp;
| ^ slice indices are of type `usize` or ranges of `usize`
|
= help: the trait `SliceIndex<[isize]>` is not implemented for `isize`
= help: the trait `SliceIndex<[T]>` is implemented for `usize`
= note: required for `Vec<isize>` to implement `Index<isize>`
error[E0308]: mismatched types
--> BinarySearch.rs:30:2
|
26 | fn partition(list:&mut Vec<isize>, low:isize, high:isize) -> isize {
| ----- expected `isize` because of return type
...
30 | / while true {
31 | | loop {
32 | | i += 1;
33 | | if !(list[i] < pivot) { break; }
... |
44 | | list[i] = temp;
45 | | }
| |_____^ expected `isize`, found `()`
|
note: the function expects a value to always be returned, but loops might run zero times
--> BinarySearch.rs:30:2
|
30 | while true {
| ^^^^^^^^^^ this might have zero elements to iterate on
...
40 | return j;
| -------- if the loop doesn't execute, this value would never get returned
= help: return a value for the case when the loop has zero elements to iterate on, or consider changing the return type to account for that possibility
error[E0308]: mismatched types
--> BinarySearch.rs:57:27
|
57 | quicksort0(&mut list, 0, list.len() - 1);
| ---------- ^^^^^^^^^^^^^^ expected `isize`, found `usize`
| |
| arguments to this function are incorrect
|
note: function defined here
--> BinarySearch.rs:48:4
|
48 | fn quicksort0(list:&mut Vec<isize>, low:isize, high:isize) -> () {
| ^^^^^^^^^^ ----------
help: you can convert a `usize` to an `isize` and panic if the converted value doesn't fit
|
57 | quicksort0(&mut list, 0, (list.len() - 1).try_into().unwrap());
| + +++++++++++++++++++++
error[E0425]: cannot find function `clock_millis` in this scope
--> BinarySearch.rs:76:22
|
76 | let mut start:i64 = clock_millis();
| ^^^^^^^^^^^^ not found in this scope
error[E0425]: cannot find function `clock_millis` in this scope
--> BinarySearch.rs:84:21
|
84 | let mut stop:i64 = clock_millis();
| ^^^^^^^^^^^^ not found in this scope
error[E0425]: cannot find function `clock_millis` in this scope
--> BinarySearch.rs:88:10
|
88 | start = clock_millis();
| ^^^^^^^^^^^^ not found in this scope
error[E0425]: cannot find function `clock_millis` in this scope
--> BinarySearch.rs:90:9
|
90 | stop = clock_millis();
| ^^^^^^^^^^^^ not found in this scope
error[E0425]: cannot find function `clock_millis` in this scope
--> BinarySearch.rs:94:10
|
94 | start = clock_millis();
| ^^^^^^^^^^^^ not found in this scope
error[E0277]: the type `[isize]` cannot be indexed by `isize`
--> BinarySearch.rs:98:50
|
98 | let pos:isize = binarySearch(samples, samples[i]);
| ^ slice indices are of type `usize` or ranges of `usize`
|
= help: the trait `SliceIndex<[isize]>` is not implemented for `isize`
= help: the trait `SliceIndex<[T]>` is implemented for `usize`
= note: required for `Vec<isize>` to implement `Index<isize>`
error[E0425]: cannot find function `clock_millis` in this scope
--> BinarySearch.rs:103:9
|
103 | stop = clock_millis();
| ^^^^^^^^^^^^ not found in this scope
error: aborting due to 24 previous errors; 1 warning emitted
Some errors have detailed explanations: E0277, E0308, E0425.
For more information about an error, try `rustc --explain E0277`.
$ rustc BinarySearch.rs
error: unknown format trait `d`
--> BinarySearch.rs:85:39
|
85 | println!("{}", format!("Duration: {0:d} ms", stop - start));
| ^
|
= note: the only appropriate formatting traits are:
- ``, which uses the `Display` trait
- `?`, which uses the `Debug` trait
- `e`, which uses the `LowerExp` trait
- `E`, which uses the `UpperExp` trait
- `o`, which uses the `Octal` trait
- `p`, which uses the `Pointer` trait
- `b`, which uses the `Binary` trait
- `x`, which uses the `LowerHex` trait
- `X`, which uses the `UpperHex` trait
error: unknown format trait `d`
--> BinarySearch.rs:91:39
|
91 | println!("{}", format!("Duration: {0:d} ms", stop - start));
| ^
|
= note: the only appropriate formatting traits are:
- ``, which uses the `Display` trait
- `?`, which uses the `Debug` trait
- `e`, which uses the `LowerExp` trait
- `E`, which uses the `UpperExp` trait
- `o`, which uses the `Octal` trait
- `p`, which uses the `Pointer` trait
- `b`, which uses the `Binary` trait
- `x`, which uses the `LowerHex` trait
- `X`, which uses the `UpperHex` trait
error: unknown format trait `d`
--> BinarySearch.rs:104:39
|
104 | println!("{}", format!("Duration: {0:d} ms", stop - start));
| ^
|
= note: the only appropriate formatting traits are:
- ``, which uses the `Display` trait
- `?`, which uses the `Debug` trait
- `e`, which uses the `LowerExp` trait
- `E`, which uses the `UpperExp` trait
- `o`, which uses the `Octal` trait
- `p`, which uses the `Pointer` trait
- `b`, which uses the `Binary` trait
- `x`, which uses the `LowerHex` trait
- `X`, which uses the `UpperHex` trait
error[E0425]: cannot find function `exit` in this scope
--> BinarySearch.rs:70:3
|
70 | exit(1);
| ^^^^ not found in this scope
|
help: consider importing this function
|
8 + use std::process::exit;
|
error[E0425]: cannot find value `Utils` in this scope
--> BinarySearch.rs:72:29
|
72 | let mut sampleSize:isize = Utils.stoiWithDefault(args[1], 10);
| ^^^^^ not found in this scope
warning: denote infinite loops with `loop { ... }`
--> BinarySearch.rs:30:2
|
30 | while true {
| ^^^^^^^^^^ help: use `loop`
|
= note: `#[warn(while_true)]` on by default
error[E0308]: mismatched types
--> BinarySearch.rs:12:24
|
12 | let mut right:isize = list.len() - 1;
| ----- ^^^^^^^^^^^^^^ expected `isize`, found `usize`
| |
| expected due to this
|
help: you can convert a `usize` to an `isize` and panic if the converted value doesn't fit
|
12 | let mut right:isize = (list.len() - 1).try_into().unwrap();
| + +++++++++++++++++++++
error[E0277]: the type `[isize]` cannot be indexed by `isize`
--> BinarySearch.rs:15:11
|
15 | if list[m] < value {
| ^ slice indices are of type `usize` or ranges of `usize`
|
= help: the trait `SliceIndex<[isize]>` is not implemented for `isize`
= help: the trait `SliceIndex<[T]>` is implemented for `usize`
= note: required for `Vec<isize>` to implement `Index<isize>`
error[E0277]: the type `[isize]` cannot be indexed by `isize`
--> BinarySearch.rs:17:18
|
17 | } else if list[m] > value {
| ^ slice indices are of type `usize` or ranges of `usize`
|
= help: the trait `SliceIndex<[isize]>` is not implemented for `isize`
= help: the trait `SliceIndex<[T]>` is implemented for `usize`
= note: required for `Vec<isize>` to implement `Index<isize>`
error[E0277]: the type `[isize]` cannot be indexed by `isize`
--> BinarySearch.rs:27:25
|
27 | let pivot:isize = list[(high + low) / 2];
| ^^^^^^^^^^^^^^^^ slice indices are of type `usize` or ranges of `usize`
|
= help: the trait `SliceIndex<[isize]>` is not implemented for `isize`
= help: the trait `SliceIndex<[T]>` is implemented for `usize`
= note: required for `Vec<isize>` to implement `Index<isize>`
error[E0277]: the type `[isize]` cannot be indexed by `isize`
--> BinarySearch.rs:33:14
|
33 | if !(list[i] < pivot) { break; }
| ^ slice indices are of type `usize` or ranges of `usize`
|
= help: the trait `SliceIndex<[isize]>` is not implemented for `isize`
= help: the trait `SliceIndex<[T]>` is implemented for `usize`
= note: required for `Vec<isize>` to implement `Index<isize>`
error[E0277]: the type `[isize]` cannot be indexed by `isize`
--> BinarySearch.rs:37:14
|
37 | if !(list[j] > pivot) { break; }
| ^ slice indices are of type `usize` or ranges of `usize`
|
= help: the trait `SliceIndex<[isize]>` is not implemented for `isize`
= help: the trait `SliceIndex<[T]>` is implemented for `usize`
= note: required for `Vec<isize>` to implement `Index<isize>`
error[E0277]: the type `[isize]` cannot be indexed by `isize`
--> BinarySearch.rs:42:25
|
42 | let temp:isize = list[j];
| ^ slice indices are of type `usize` or ranges of `usize`
|
= help: the trait `SliceIndex<[isize]>` is not implemented for `isize`
= help: the trait `SliceIndex<[T]>` is implemented for `usize`
= note: required for `Vec<isize>` to implement `Index<isize>`
error[E0277]: the type `[isize]` cannot be indexed by `isize`
--> BinarySearch.rs:43:8
|
43 | list[j] = list[i];
| ^ slice indices are of type `usize` or ranges of `usize`
|
= help: the trait `SliceIndex<[isize]>` is not implemented for `isize`
= help: the trait `SliceIndex<[T]>` is implemented for `usize`
= note: required for `Vec<isize>` to implement `Index<isize>`
error[E0277]: the type `[isize]` cannot be indexed by `isize`
--> BinarySearch.rs:43:18
|
43 | list[j] = list[i];
| ^ slice indices are of type `usize` or ranges of `usize`
|
= help: the trait `SliceIndex<[isize]>` is not implemented for `isize`
= help: the trait `SliceIndex<[T]>` is implemented for `usize`
= note: required for `Vec<isize>` to implement `Index<isize>`
error[E0277]: the type `[isize]` cannot be indexed by `isize`
--> BinarySearch.rs:44:8
|
44 | list[i] = temp;
| ^ slice indices are of type `usize` or ranges of `usize`
|
= help: the trait `SliceIndex<[isize]>` is not implemented for `isize`
= help: the trait `SliceIndex<[T]>` is implemented for `usize`
= note: required for `Vec<isize>` to implement `Index<isize>`
error[E0308]: mismatched types
--> BinarySearch.rs:30:2
|
26 | fn partition(list:&mut Vec<isize>, low:isize, high:isize) -> isize {
| ----- expected `isize` because of return type
...
30 | / while true {
31 | | loop {
32 | | i += 1;
33 | | if !(list[i] < pivot) { break; }
... |
44 | | list[i] = temp;
45 | | }
| |_____^ expected `isize`, found `()`
|
note: the function expects a value to always be returned, but loops might run zero times
--> BinarySearch.rs:30:2
|
30 | while true {
| ^^^^^^^^^^ this might have zero elements to iterate on
...
40 | return j;
| -------- if the loop doesn't execute, this value would never get returned
= help: return a value for the case when the loop has zero elements to iterate on, or consider changing the return type to account for that possibility
error[E0308]: mismatched types
--> BinarySearch.rs:57:27
|
57 | quicksort0(&mut list, 0, list.len() - 1);
| ---------- ^^^^^^^^^^^^^^ expected `isize`, found `usize`
| |
| arguments to this function are incorrect
|
note: function defined here
--> BinarySearch.rs:48:4
|
48 | fn quicksort0(list:&mut Vec<isize>, low:isize, high:isize) -> () {
| ^^^^^^^^^^ ----------
help: you can convert a `usize` to an `isize` and panic if the converted value doesn't fit
|
57 | quicksort0(&mut list, 0, (list.len() - 1).try_into().unwrap());
| + +++++++++++++++++++++
error[E0425]: cannot find function `clock_millis` in this scope
--> BinarySearch.rs:76:22
|
76 | let mut start:i64 = clock_millis();
| ^^^^^^^^^^^^ not found in this scope
error[E0425]: cannot find function `clock_millis` in this scope
--> BinarySearch.rs:84:21
|
84 | let mut stop:i64 = clock_millis();
| ^^^^^^^^^^^^ not found in this scope
error[E0425]: cannot find function `clock_millis` in this scope
--> BinarySearch.rs:88:10
|
88 | start = clock_millis();
| ^^^^^^^^^^^^ not found in this scope
error[E0425]: cannot find function `clock_millis` in this scope
--> BinarySearch.rs:90:9
|
90 | stop = clock_millis();
| ^^^^^^^^^^^^ not found in this scope
error[E0425]: cannot find function `clock_millis` in this scope
--> BinarySearch.rs:94:10
|
94 | start = clock_millis();
| ^^^^^^^^^^^^ not found in this scope
error[E0277]: the type `[isize]` cannot be indexed by `isize`
--> BinarySearch.rs:98:50
|
98 | let pos:isize = binarySearch(samples, samples[i]);
| ^ slice indices are of type `usize` or ranges of `usize`
|
= help: the trait `SliceIndex<[isize]>` is not implemented for `isize`
= help: the trait `SliceIndex<[T]>` is implemented for `usize`
= note: required for `Vec<isize>` to implement `Index<isize>`
error[E0425]: cannot find function `clock_millis` in this scope
--> BinarySearch.rs:103:9
|
103 | stop = clock_millis();
| ^^^^^^^^^^^^ not found in this scope
error: aborting due to 24 previous errors; 1 warning emitted
Some errors have detailed explanations: E0277, E0308, E0425.
For more information about an error, try `rustc --explain E0277`.