Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Given a sorted array of size N and an integer K, find the position at which K is present in the array using binary search in Rust
struct Solution;
impl Solution {
fn new() -> Solution { Self }
fn binary_search(&self, arr: &[i32], n: usize, k: i32) -> i32 {
let mut low = 0;
let mut high = n - 1;
while low <= high {
let mid = low + (high - low) / 2;
if arr[mid] == k {
return mid as i32;
} else if arr[mid] < k {
low = mid + 1
} else if arr[mid] > k {
high = mid - 1
}
}
-1
}
}
#[cfg(test)]
mod test {
use super::*;
#[test]
fn case_1() {
let s = Solution::new();
let n = 59;
let arr = "1 2 3 4 5 6 8 9 10 14 16 19 22 23 25 26 27 29 31 34 35 36 38 39 40 45 46 48 50 51 52 57 59 60 61 63 67 68 69 71 75 76 77 79 81 82 83 86 87 88 90 92 93 94 95 96 98 99 100".split(" ").into_iter().filter_map(|x| x.parse::<i32>().ok()).collect::<Vec<i32>>();
let k = 93;
let r = 52;
assert_eq!(s.binary_search(&arr, n, k), r);
}
#[test]
fn case_2() {
let s = Solution::new();
let n = 5;
let arr = "1 2 3 4 5".split(" ").into_iter().filter_map(|x| x.parse::<i32>().ok()).collect::<Vec<i32>>();
let k = 4;
let r = 3;
assert_eq!(s.binary_search(&arr, n, k), r);
}
#[test]
fn case_3() {
let s = Solution::new();
let n = 5;
let arr = "1 2 3 4 5".split(" ").into_iter().filter_map(|x| x.parse::<i32>().ok()).collect::<Vec<i32>>();
let k = 60;
let r = -1;
assert_eq!(s.binary_search(&arr, n, k), r);
}
}

Given a sorted array of size N and an integer K, find the position at which K is present in the array using binary search.

Example 1:

Input: N = 5 arr[] = {1 2 3 4 5} K = 4 Output: 3 Explanation: 4 appears at index 3.

Example 2:

Input: N = 5 arr[] = {11 22 33 44 55} K = 445 Output: -1 Explanation: 445 is not present.

Your Task:
You dont need to read input or print anything. Complete the function binarysearch() which takes arr[], N and K as input parameters and returns the index of K in the array. If K is not present in the array, return -1.

Expected Time Complexity: O(LogN) Expected Auxiliary Space: O(LogN) if solving recursively and O(1) otherwise.

Constraints:

1 <= N <= 105 1 <= arr[i] <= 106 1 <= K <= 106

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment