Instantly share code, notes, and snippets.

# mikhail-krainik/binary_search.rs

Created Nov 3, 2022
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
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 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::().ok()).collect::>(); 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::().ok()).collect::>(); 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::().ok()).collect::>(); 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.