## Tag Archives: binary search

## C# || How To Find The Minimum Speed To Arrive On Time Using C#

The following is a module with functions which demonstrates how to find the minimum speed to arrive on time using C#.

1. Min Speed On Time – Problem Statement

You are given a floating-point number **hour**, representing the amount of time you have to reach the office. To commute to the office, you must take **n** trains in sequential order. You are also given an integer array **dist** of length **n**, where **dist[i]** describes the distance (in kilometers) of the **i ^{th}** train ride.

Each train can only depart at an integer hour, so you may need to wait in between each train ride.

- For example, if the
**1**train ride takes^{st}**1.5**hours, you must wait for an additional**0.5**hours before you can depart on the**2**train ride at the 2 hour mark.^{nd}

Return *the minimum positive integer speed (in kilometers per hour) that all the trains must travel at for you to reach the office on time, or *

**-1**

*if it is impossible to be on time*.

Tests are generated such that the answer will not exceed **10 ^{7}** and

**hour**will have

**at most two digits after the decimal point**.

**Example 1:**

Input:dist = [1,3,2], hour = 6

Output:1

Explanation:At speed 1:

- The first train ride takes 1/1 = 1 hour.

- Since we are already at an integer hour, we depart immediately at the 1 hour mark. The second train takes 3/1 = 3 hours.

- Since we are already at an integer hour, we depart immediately at the 4 hour mark. The third train takes 2/1 = 2 hours.

- You will arrive at exactly the 6 hour mark.

**Example 2:**

Input:dist = [1,3,2], hour = 2.7

Output:3

Explanation:At speed 3:

- The first train ride takes 1/3 = 0.33333 hours.

- Since we are not at an integer hour, we wait until the 1 hour mark to depart. The second train ride takes 3/3 = 1 hour.

- Since we are already at an integer hour, we depart immediately at the 2 hour mark. The third train takes 2/3 = 0.66667 hours.

- You will arrive at the 2.66667 hour mark.

**Example 3:**

Input:dist = [1,3,2], hour = 1.9

Output:-1

Explanation:It is impossible because the earliest the third train can depart is at the 2 hour mark.

2. Min Speed On Time – Solution

The following is a solution which demonstrates how to find the minimum speed to arrive on time.

```
```
1234567891011121314151617181920212223242526272829303132333435363738
// ============================================================================// Author: Kenneth Perkins// Date: Sep 1, 2023// Taken From: http://programmingnotes.org/// File: Solution.cs// Description: Demonstrates how to find the minimum speed to arrive on time// ============================================================================public class Solution { public int MinSpeedOnTime(int[] dist, double hour) { int left = 1; int right = 10000000; int minSpeed = -1; while (left <= right) { int mid = left + (right - left) / 2; // Move to the left half. if (TimeRequired(dist, mid) <= hour) { minSpeed = mid; right = mid - 1; } else { // Move to the right half. left = mid + 1; } } return minSpeed; } double TimeRequired(int[] dist, int speed) { double time = 0.0; for (int i = 0 ; i < dist.Length; i++) { double t = (double) dist[i] / (double) speed; // Round off to the next integer, if not the last ride. time += (i == dist.Length - 1 ? t : Math.Ceiling(t)); } return time; }}// http://programmingnotes.org/

**QUICK NOTES**:

The highlighted lines are sections of interest to look out for.

The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.

Once compiled, you should get this as your output for the example cases:

1

3

-1

## C# || How To Find The Maximum Profit In Job Scheduling Using C#

The following is a module with functions which demonstrates how to find the maximum profit in job scheduling using C#.

1. Job Scheduling – Problem Statement

We have **n** jobs, where every job is scheduled to be done from **startTime[i]** to **endTime[i]**, obtaining a profit of **profit[i]**.

You’re given the **startTime**, **endTime** and **profit** arrays, return the maximum profit you can take such that there are no two jobs in the subset with overlapping time range.

If you choose a job that ends at time **X** you will be able to start another job that starts at time **X**.

**Example 1:**

Input:startTime = [1,2,3,3], endTime = [3,4,5,6], profit = [50,10,40,70]

Output:120

Explanation:The subset chosen is the first and fourth job.

Time range [1-3]+[3-6] , we get profit of 120 = 50 + 70.

**Example 2:**

Input:startTime = [1,2,3,4,6], endTime = [3,5,10,6,9], profit = [20,20,100,70,60]

Output:150

Explanation:The subset chosen is the first, fourth and fifth job.

Profit obtained 150 = 20 + 70 + 60.

**Example 3:**

Input:startTime = [1,1,1], endTime = [2,3,4], profit = [5,6,4]

Output:6

2. Job Scheduling – Solution

The following is a solution which demonstrates how to find the maximum profit in job scheduling.

```
```
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071
// ============================================================================// Author: Kenneth Perkins// Date: Jan 1, 2023// Taken From: http://programmingnotes.org/// File: Solution.cs// Description: Demonstrates how to find maximum profit in job scheduling// ============================================================================public class Solution { public int JobScheduling(int[] startTime, int[] endTime, int[] profit) { if (startTime == null || startTime.Length == 0) { return 0; } var jobs = new List<Job>(); for (int index = 0; index < startTime.Length; ++index) { jobs.Add(new Job(startTime[index], endTime[index], profit[index])); } jobs.Sort((a, b) => a.Start - b.Start); return DFS(jobs, 0, new Dictionary<int, int>()); } private int DFS(List<Job> jobs, int currentJobIndex, Dictionary<int, int> maxProfits) { if (currentJobIndex >= jobs.Count) { return 0; } if (maxProfits.ContainsKey(currentJobIndex)) { return maxProfits[currentJobIndex]; } int next = BinarySearch(jobs, currentJobIndex); int inc = jobs[currentJobIndex].Profit + (next == -1 ? 0 : DFS(jobs, next, maxProfits)); int exc = DFS(jobs, currentJobIndex + 1, maxProfits); int maxProfit = Math.Max(inc, exc); maxProfits[currentJobIndex] = maxProfit; return maxProfit; } private int BinarySearch(List<Job> jobs, int currentJobIndex) { int lo = currentJobIndex; int high = jobs.Count - 1; int result = -1; while (lo <= high) { int mid = lo + (high - lo) / 2; if (jobs[currentJobIndex].End <= jobs[mid].Start) { result = mid; high = mid - 1; } else { lo = mid + 1; } } return result; } class Job { public int Start { get; set; } public int End { get; set; } public int Profit { get; set; } public Job(int startTime, int endTime, int profit) { Start = startTime; End = endTime; Profit = profit; } }}// http://programmingnotes.org/

**QUICK NOTES**:

The highlighted lines are sections of interest to look out for.

The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.

Once compiled, you should get this as your output for the example cases:

120

150

6

## C# || How To Design A Time Based Key-Value Store To Retrieve Timestamps Using C#

The following is a module with functions which demonstrates how to design a time based key-value store to retrieve timestamps using C#.

1. Time Map – Problem Statement

Design a time-based key-value data structure that can store multiple values for the same key at different time stamps and retrieve the key’s value at a certain timestamp.

Implement the **TimeMap** class:

**TimeMap()**Initializes the object of the data structure.**void set(String key, String value, int timestamp)**Stores the key**key**with the value**value**at the given time**timestamp**.**String get(String key, int timestamp)**Returns a value such that**set**was called previously, with**timestamp_prev <= timestamp**. If there are multiple such values, it returns the value associated with the largest**timestamp_prev**. If there are no values, it returns**“”**.

**Example 1:**

Input

["TimeMap", "set", "get", "get", "set", "get", "get"]

[[], ["foo", "bar", 1], ["foo", 1], ["foo", 3], ["foo", "bar2", 4], ["foo", 4], ["foo", 5]]

Output

[null, null, "bar", "bar", null, "bar2", "bar2"]

Explanation

TimeMap timeMap = new TimeMap();

timeMap.set("foo", "bar", 1); // store the key "foo" and value "bar" along with timestamp = 1.

timeMap.get("foo", 1); // return "bar"

timeMap.get("foo", 3); // return "bar", since there is no value corresponding to foo at timestamp 3 and timestamp 2, then the only value is at timestamp 1 is "bar".

timeMap.set("foo", "bar2", 4); // store the key "foo" and value "bar2" along with timestamp = 4.

timeMap.get("foo", 4); // return "bar2"

timeMap.get("foo", 5); // return "bar2"

2. Time Map – Solution

The following is a solution which demonstrates how to design a time based key-value store to retrieve timestamps.

```
```
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859
// ============================================================================// Author: Kenneth Perkins// Date: Nov 1, 2022// Taken From: http://programmingnotes.org/// File: Solution.cs// Description: Demonstrates how to design a time map// ============================================================================/** * Your TimeMap object will be instantiated and called as such: * TimeMap obj = new TimeMap(); * obj.Set(key,value,timestamp); * string param_2 = obj.Get(key,timestamp); */public class TimeMap { private class Data { public string value; public int timestamp; public Data(string value, int timestamp) { this.value = value; this.timestamp = timestamp; } } private Dictionary<string, List<Data>> map; public TimeMap() { map = new Dictionary<string, List<Data>>(); } public void Set(string key, string value, int timestamp) { if (!map.ContainsKey(key)) { map.Add(key, new List<Data>()); } map[key].Add(new Data(value, timestamp)); } public string Get(string key, int timestamp) { if (!map.ContainsKey(key)) { return ""; } return BinarySearch(map[key], timestamp); } string BinarySearch(List<Data> bucket, int target) { int low = 0, high = bucket.Count; while (low < high) { int mid = low + (high - low) / 2; if (bucket[mid].timestamp <= target) { low = mid + 1; } else { high = mid; } } if (high == 0) { return ""; } return (bucket[high - 1].timestamp <= target) ? bucket[high - 1].value : ""; }}// http://programmingnotes.org/

**QUICK NOTES**:

The highlighted lines are sections of interest to look out for.

The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.

Once compiled, you should get this as your output for the example cases:

[null,null,"bar","bar",null,"bar2","bar2"]

## C# || How To Search In Rotated Sorted Array Using C#

The following is a module with functions which demonstrates how to search for a target value in a rotated sorted array using C#.

1. Search – Problem Statement

There is an integer array **nums** sorted in ascending order (with **distinct** values).

Prior to being passed to your function, **nums** is **possibly rotated** at an unknown pivot index **k** (**1 <= k < nums.length**) such that the resulting array is **[nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]]** (**0-indexed**). For example, **[0,1,2,4,5,6,7]** might be rotated at pivot index **3** and become **[4,5,6,7,0,1,2]**.

Given the array **nums** **after** the possible rotation and an integer **target**, return *the index of ***target*** if it is in ***nums***, or ***-1*** if it is not in ***nums**.

You must write an algorithm with **O(log n)** runtime complexity.

**Example 1:**

Input: nums = [4,5,6,7,0,1,2], target = 0

Output: 4

**Example 2:**

Input: nums = [4,5,6,7,0,1,2], target = 3

Output: -1

**Example 3:**

Input: nums = [1], target = 0

Output: -1

2. Search – Solution

The following is a solution which demonstrates how to search for a target value in a rotated sorted array.

The idea of this solution is to use binary search, and for each loop iteration we compare the midpoint element with the right side of the array to determine the search area of where the target element might be.

```
```
1234567891011121314151617181920212223242526272829303132333435363738394041
// ============================================================================// Author: Kenneth Perkins// Date: Nov 26, 2021// Taken From: http://programmingnotes.org/// File: Solution.cs// Description: Demonstrates how to search for a target in a rotated array// ============================================================================public class Solution { public int Search(int[] nums, int target) { var lo = 0; var hi = nums.Length - 1; while (lo <= hi) { var mid = lo + (hi - lo) / 2; // Target element found if (nums[mid] == target) { return mid; // Midpoint element is greater than right side of array } else if (nums[mid] > nums[hi]) { // Determine which side of array to adjust if (target < nums[mid] && target >= nums[lo]) { hi = mid - 1; } else { lo = mid + 1; } // Midpoint element is less than right side of array } else { // Determine which side of array to adjust if (target > nums[mid] && target <= nums[hi]) { lo = mid + 1; } else { hi = mid - 1; } } } return -1; }}// http://programmingnotes.org/

**QUICK NOTES**:

The highlighted lines are sections of interest to look out for.

Once compiled, you should get this as your output for the example cases:

4

-1

-1

## C# || How To Find Single Element In A Sorted Array Using C#

The following is a module with functions which demonstrates how to find a single element in a sorted array using C#.

1. Single Non Duplicate – Problem Statement

You are given a sorted array consisting of only integers where every element appears exactly twice, except for one element which appears exactly once.

Return *the single element that appears only once*.

Your solution must run in **O(log n)** time and **O(1)** space.

**Example 1:**

Input: nums = [1,1,2,3,3,4,4,8,8]

Output: 2

**Example 2:**

Input: nums = [3,3,7,7,10,11,11]

Output: 10

2. Single Non Duplicate – Solution

The following is a solution which demonstrates how to find a single element in a sorted array.

The idea of this solution is the following:

Suppose we have the following array: `[1,1,2,2,3,3,4,4,6,8,8]`

We can observe that for each pair:

- The first pair element takes the even array index position
- The second pair element takes the odd array index position

For example, when examining the number 1 as a pair, we see it takes the array index positions 0 and 1.

Similarly for all other pairs, the first pair element takes the even array index position, and the second pair element takes the odd array index position.

Using this idea, we can see that this pattern for pairs will break when a single element appears in the array.

In this solution, we use binary search to look for the point in the array where the pattern mentioned above for the pairs first breaks

```
```
1234567891011121314151617181920212223242526272829303132
// ============================================================================// Author: Kenneth Perkins// Date: Nov 19, 2021// Taken From: http://programmingnotes.org/// File: Solution.cs// Description: Demonstrates how to find a single element in a sorted array// ============================================================================public class Solution { public int SingleNonDuplicate(int[] nums) { var lo = 0; var hi = nums.Length - 1; while (lo < hi) { // Get the mipoint var mid = lo + (hi - lo) / 2; // Check to see if mid is even var isEven = mid % 2 == 0; // If mid is even, its duplicate should be the next index // If mid is odd, its duplicate should be the previous index if ((isEven && nums[mid] == nums[mid + 1]) || (!isEven && nums[mid] == nums[mid - 1])) { // Duplicate found, advance to next index. Single element is > mid lo = mid + 1; } else { // Pattern is broken. Single element is <= mid hi = mid; } } return nums[lo]; }}// http://programmingnotes.org/

**QUICK NOTES**:

The highlighted lines are sections of interest to look out for.

Once compiled, you should get this as your output for the example cases:

2

10

## C# || How To Find Friends Of Appropriate Ages Using C#

The following is a module with functions which demonstrates how to find friends of appropriate ages using C#.

1. Num Friend Requests – Problem Statement

There are **n** persons on a social media website. You are given an integer array **ages** where **ages[i]** is the age of the **i ^{th}** person.

A Person **x** will not send a friend request to a person **y** (**x != y**) if any of the following conditions is true:

**age[y] <= 0.5 * age[x] + 7****age[y] > age[x]****age[y] > 100 && age[x] < 100**

Otherwise, **x** will send a friend request to **y**.

Note that if **x** sends a request to **y**, **y** will not necessarily send a request to **x**. Also, a person will not send a friend request to themself.

Return *the total number of friend requests made*.

**Example 1:**

Input: ages = [16,16]

Output: 2

Explanation: 2 people friend request each other.

**Example 2:**

Input: ages = [16,17,18]

Output: 2

Explanation: Friend requests are made 17 -> 16, 18 -> 17.

**Example 3:**

Input: ages = [20,30,100,110,120]

Output: 3

Explanation: Friend requests are made 110 -> 100, 120 -> 110, 120 -> 100.

2. Num Friend Requests – Solution

The following is a solution which demonstrates how to find friends of appropriate ages.

In this solution, we sort the ages and use a map that keeps track of the ages, and the total friend request count that age can recieve.

Binary search is used to get the age range in the array that satisfies the friend request conditions for a given age.

```
```
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748
// ============================================================================// Author: Kenneth Perkins// Date: Nov 5, 2021// Taken From: http://programmingnotes.org/// File: Solution.cs// Description: Demonstrates how to find friends of appropriate ages// ============================================================================public class Solution { public int NumFriendRequests(int[] ages) { var result = 0; // Sort ages Array.Sort(ages); // Keep track of results calculated var seen = new Dictionary<int, int>(); // Iterate array backwards for (int index = ages.Length - 1; index >= 0; --index) { // Check if we already calculated result for age if (!seen.ContainsKey(ages[index])) { // Binary search var lo = 0; var hi = index; while (lo < hi) { var mid = lo + (hi - lo) / 2; // Check if friends can be made in this range if (!CanFriend(ages[index], ages[mid])) { lo = mid + 1; } else { hi = mid; } } // Get distance between index and hi. This is the friend count for the age seen[ages[index]] = index - hi; } // Update result count result += seen[ages[index]]; } return result; } private bool CanFriend(int x, int y) { return !((y > x) || (y > 100 && x < 100) || (y <= 0.5 * x + 7)); }}// http://programmingnotes.org/

**QUICK NOTES**:

The highlighted lines are sections of interest to look out for.

Once compiled, you should get this as your output for the example cases:

2

2

3

## C# || How To Traverse Binary Tree Zigzag Level Order Using C#

The following is a module with functions which demonstrates how to traverse binary tree zigzag level order using C#.

1. Zigzag Level Order – Problem Statement

Given the **root** of a binary tree, return *the zigzag level order traversal of its nodes’ values*. (i.e., from left to right, then right to left for the next level and alternate between).

**Example 1:**

Input: root = [3,9,20,null,null,15,7]

Output: [[3],[20,9],[15,7]]

**Example 2:**

Input: root = [1]

Output: [[1]]

**Example 3:**

Input: root = []

Output: []

2. Zigzag Level Order – Solution

The following is a solution which demonstrates how to traverse binary tree zigzag level order.

This solution uses Breadth First Search to explore items at each level.

```
```
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576
// ============================================================================// Author: Kenneth Perkins// Date: Oct 29, 2021// Taken From: http://programmingnotes.org/// File: Solution.cs// Description: Demonstrates how to traverse a tree zigzag level order// ============================================================================/** * Definition for a binary tree node. * public class TreeNode { * public int val; * public TreeNode left; * public TreeNode right; * public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) { * this.val = val; * this.left = left; * this.right = right; * } * } */public class Solution { public IList<IList<int>> ZigzagLevelOrder(TreeNode root) { var result = new List<IList<int>>(); var stack = new Stack<TreeNode>(); // Add root to stack if (root != null) { stack.Push(root); } var leftToRight = true; while (stack.Count > 0) { var queue = new Queue<TreeNode>(); var level = new List<int>(); // Add items at the top of the stack to the current level for (var itemCount = stack.Count; itemCount > 0; --itemCount) { var current = stack.Peek(); stack.Pop(); level.Add(current.val); queue.Enqueue(current); } // Add level to result result.Add(level); // Go through items in the queue and add them to the stack in the proper order for (var itemCount = queue.Count; itemCount > 0; --itemCount) { var current = queue.Peek(); queue.Dequeue(); // Add children to the stack // Left to right or Right to left order if (leftToRight) { if (current.left != null) { stack.Push(current.left); } if (current.right != null) { stack.Push(current.right); } } else { if (current.right != null) { stack.Push(current.right); } if (current.left != null) { stack.Push(current.left); } } } // Alternate order for the next level leftToRight = !leftToRight; } return result; }}// http://programmingnotes.org/

**QUICK NOTES**:

The highlighted lines are sections of interest to look out for.

Once compiled, you should get this as your output for the example cases:

[[3],[20,9],[15,7]]

[[1]]

[]

## C# || How To Find Longest Duplicate Substring Using C#

The following is a module with functions which demonstrates how to find the longest duplicate substring using C#.

1. Longest Dup Substring – Problem Statement

Given a string **s**, consider all *duplicated substrings*: (contiguous) substrings of s that occur 2 or more times. The occurrences may overlap.

Return **any** duplicated substring that has the longest possible length. If **s** does not have a duplicated substring, the answer is **“”**.

**Example 1:**

Input: s = "banana"

Output: "ana"

**Example 2:**

Input: s = "abcd"

Output: ""

2. Longest Dup Substring – Solution

The following is a solution which demonstrates how find the longest duplicate substring.

This solution uses Binary Search and Rolling Hash.

```
```
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091
// ============================================================================// Author: Kenneth Perkins// Date: Oct 30, 2021// Taken From: http://programmingnotes.org/// File: Solution.cs// Description: Demonstrates how to find the longest duplicate substring// ============================================================================public class Solution { public string LongestDupSubstring(string s) { // Convert string to array of ascii integers // to implement constant time slice var nums = new int[s.Length]; for (int index = 0; index < s.Length; ++index) { nums[index] = (int)s[index] - (int)'a'; } // Keeps track of substring start index and length var startIndex = -1; var substrLength = -1; // Use binary search to find the largest possible length of a duplicate substring var left = 1; var right = s.Length; while (left < right) { var mid = left + (right - left) / 2; // Rolling hash (Rabin-Karp) var index = RollingSearch(nums, mid); // Substring found if (index != -1) { if (mid > substrLength) { startIndex = index; substrLength = mid; } left = mid + 1; // Substring not found } else { right = mid; } } return substrLength != -1 ? s.Substring(startIndex, substrLength): ""; } private int RollingSearch(int[] nums, int mid) { var seen = new HashSet<long>(); // Base value for the rolling hash function var a = 31; // Current hash var hash = Hash(nums, mid, a); seen.Add(hash); long pow = 1; for (var index = 1; index < mid; ++index) { pow *= a; } var result = -1; for (var index = 1; index < nums.Length - mid + 1; ++index) { // Compute rolling hash hash = RollingHash(pow, hash, nums[index - 1], nums[index + mid - 1], a); // Hash found if (seen.Contains(hash)) { result = index; break; } // Hash not found seen.Add(hash); } return result; } private long Hash(int[] nums, int mid, int a) { long h = 0; long aL = 1; for (var index = mid; index >= 1; --index) { h += (nums[index - 1] + 1) * aL; aL *= a; } return h; } private long RollingHash(long pow, long hash, int left, int right, int a) { return (hash - (left + 1) * pow) * a + (right + 1); }}// http://programmingnotes.org/

**QUICK NOTES**:

The highlighted lines are sections of interest to look out for.

Once compiled, you should get this as your output for the example cases:

"ana"

""

## C# || Two Sum II – How To Get Two Numbers In Sorted Array Equal To Target Value Using C#

The following is a module with functions which demonstrates how to get two numbers in a sorted array equal to target value using C#.

1. Two Sum II – Problem Statement

Given a **1-indexed** array of integers **numbers** that is already ** sorted in non-decreasing order**, find two numbers such that they add up to a specific

**target**number. Let these two numbers be

**numbers[index**and

_{1}]**numbers[index**where

_{2}]**1 <= index**.

_{1}< index_{2}<= numbers.lengthReturn* the indices of the two numbers, ***index _{1}**

*and*

**index**

_{2}*,*

**added by one**as an integer array**[index**

_{1}, index_{2}]*of length 2.*

The tests are generated such that there is **exactly one solution**. You **may not** use the same element twice.

**Example 1:**

Input: numbers = [2,7,11,15], target = 9

Output: [1,2]

Explanation: The sum of 2 and 7 is 9. Therefore, index1 = 1, index2 = 2. We return [1, 2].

**Example 2:**

Input: numbers = [2,3,4], target = 6

Output: [1,3]

Explanation: The sum of 2 and 4 is 6. Therefore index1 = 1, index2 = 3. We return [1, 3].

**Example 3:**

Input: numbers = [-1,0], target = -1

Output: [1,2]

Explanation: The sum of -1 and 0 is -1. Therefore index1 = 1, index2 = 2. We return [1, 2].

2. Two Sum II – Solution

The following is a solution which demonstrates how to get two numbers in sorted array equal to target value.

In this solution, Binary Search is used to find the two numbers.

```
```
1234567891011121314151617181920212223242526272829303132333435363738394041424344
// ============================================================================// Author: Kenneth Perkins// Date: Oct 28, 2021// Taken From: http://programmingnotes.org/// File: Solution.cs// Description: Demonstrates how to get two numbers equal to target value// ============================================================================public class Solution { public int[] TwoSum(int[] numbers, int target) { var result = new int[2]; var lo = 0; var hi = numbers.Length - 1; while (lo < hi) { var m = lo + (hi - lo) / 2; var sum = numbers[lo] + numbers[hi]; if (sum == target) { result[0] = lo + 1; result[1] = hi + 1; break; } else if (sum < target) { // Determine if mid is less than the remaining value // Increase lo to equal mid if so if (numbers[m] < target - numbers[hi]) { lo = m + 1; } else { lo = lo + 1; } } else { // Determine if mid is greater than the remaining value // Decrease hi to equal mid if so if (numbers[m] > target - numbers[lo]) { hi = m - 1; } else { hi = hi - 1; } } } return result; }}// http://programmingnotes.org/

**QUICK NOTES**:

The highlighted lines are sections of interest to look out for.

Once compiled, you should get this as your output for the example cases:

[1,2]

[1,3]

[1,2]

## C# || How To Find Minimum In Rotated Sorted Array With Duplicates Using C#

The following is a module with functions which demonstrates how to find the minimum value in a rotated sorted array with duplicates using C#.

1. Find Min Duplicates – Problem Statement

Suppose an array of length **n** sorted in ascending order is **rotated** between **1** and **n** times. For example, the array **nums = [0,1,4,4,5,6,7]** might become:

**[4,5,6,7,0,1,4]**if it was rotated**4**times.**[0,1,4,4,5,6,7]**if it was rotated**7**times.

Notice that **rotating** an array **[a[0], a[1], a[2], …, a[n-1]]** 1 time results in the array **[a[n-1], a[0], a[1], a[2], …, a[n-2]]**.

Given the sorted rotated array **nums** that may contain **duplicates**, return *the minimum element of this array*.

You must decrease the overall operation steps as much as possible.

**Example 1:**

Input: nums = [1,3,5]

Output: 1

**Example 2:**

Input: nums = [2,2,2,0,1]

Output: 0

2. Find Min Duplicates – Solution

The following is a solution which demonstrates how to find the minimum value in a rotated sorted array with duplicates.

```
```
12345678910111213141516171819202122232425262728293031323334353637383940414243
// ============================================================================// Author: Kenneth Perkins// Date: Oct 22, 2021// Taken From: http://programmingnotes.org/// File: Solution.cs// Description: Demonstrates how to find the minimum value in a sorted array// ============================================================================public class Solution { public int FindMin(int[] nums) { var lo = 0; var hi = nums.Length - 1; // In cases where the front and back of the array are the // same (ex: [1,19,28,87,91,0,1,1,1]), decrease the end of the array while (nums[lo] == nums[hi] && lo < hi) { --hi; } // Perform binary search while (lo < hi) { var mid = lo + (hi - lo) / 2; // Midpoint element is greater than right side of array, so // the minumum element is somewhere on the right side of array. // Advance lo value to equal midpoint + 1 if (nums[mid] > nums[hi]) { lo = mid + 1; // Midpoint element is less than right side of array, so // the minumum element is somewhere on the left side of array. // Decrease hi value to equal midpoint } else if (nums[mid] < nums[hi]) { hi = mid; // Duplicate element found (nums[mid] == nums[hi]) } else { --hi; } } return nums[lo]; }}// http://programmingnotes.org/

**QUICK NOTES**:

The highlighted lines are sections of interest to look out for.

Once compiled, you should get this as your output for the example cases:

1

0

## C# || How To Find Minimum In Rotated Sorted Array Using C#

The following is a module with functions which demonstrates how to find the minimum value in a rotated sorted array using C#.

1. Find Min – Problem Statement

Suppose an array of length **n** sorted in ascending order is **rotated** between **1** and **n** times. For example, the array **nums = [0,1,2,4,5,6,7]** might become:

**[4,5,6,7,0,1,2]**if it was rotated**4**times.**[0,1,2,4,5,6,7]**if it was rotated**7**times.

Notice that **rotating** an array **[a[0], a[1], a[2], …, a[n-1]]** 1 time results in the array **[a[n-1], a[0], a[1], a[2], …, a[n-2]]**.

Given the sorted rotated array **nums** of **unique** elements, return *the minimum element of this array*.

You must write an algorithm that runs in **O(log n) time.**

**Example 1:**

Input: nums = [3,4,5,1,2]

Output: 1

Explanation: The original array was [1,2,3,4,5] rotated 3 times.

**Example 2:**

Input: nums = [4,5,6,7,0,1,2]

Output: 0

Explanation: The original array was [0,1,2,4,5,6,7] and it was rotated 4 times.

**Example 3:**

Input: nums = [11,13,15,17]

Output: 11

Explanation: The original array was [11,13,15,17] and it was rotated 4 times.

2. Find Min – Solution

The following is a solution which demonstrates how to find the minimum value in a rotated sorted array.

```
```
12345678910111213141516171819202122232425262728293031323334353637
// ============================================================================// Author: Kenneth Perkins// Date: Oct 22, 2021// Taken From: http://programmingnotes.org/// File: Solution.cs// Description: Demonstrates how to find the minimum value in a sorted array// ============================================================================public class Solution { public int FindMin(int[] nums) { var lo = 0; var hi = nums.Length - 1; while (lo < hi) { var mid = lo + (hi - lo) / 2; // Midpoint element is greater than right side of array, so // the minumum element is somewhere on the right side of array. // Advance lo value to equal midpoint + 1 if (nums[mid] > nums[hi]) { lo = mid + 1; // Midpoint element is less than right side of array, so // the minumum element is somewhere on the left side of array. // Decrease hi value to equal midpoint } else if (nums[mid] < nums[hi]) { hi = mid; // Minimum element found } else { lo = mid; break; } } return nums[lo]; }}// http://programmingnotes.org/

**QUICK NOTES**:

The highlighted lines are sections of interest to look out for.

Once compiled, you should get this as your output for the example cases:

1

0

11