Ryansblog

  A modified binary search is an algorithm that can be used to find an element in a sorted array by using a different base or condition than the standard binary search. It is an extension of the bitwise binary search and has a similar running time of O(log N) . There are different ways to modify the binary search algorithm, such as using a different number base, finding the minimum element in a rotated and sorted array, or comparing the input element with the first, last and middle elements of the array. Today we will look at rotated array problems. A rotated array is an array that is sorted in ascending order but shifted to the right by some unknown number of positions. For example, [0,1,2,4,5,6,7] is a sorted array and [4,5,6,7,0,1,2] is a rotated array with 4 positions shifted. A rotated array can also be seen as two sorted subarrays concatenated together. For example, [4,5,6,7] and [0,1,2] are two sorted subarrays that form the rotated array [4,5,6,7,0,1,2]. There are two very ...

1. Find the first and last position of a element in sorted array:   In this problem, they will gave us a sorted array and a number. We have to find out the first and last position of that element. if the target is not found, we have to return [-1,-1]. We have to solve this problem in O(log_n) time. So, we have to use binary search algorithm. Input:      nums =  [5 ,7 ,7, 8, 9, 10], target=7 Output:   [1, 2] Solution: class Solution { public:     vector < int > searchRange ( vector < int > & nums , int target ) {         int st= 0 ,en= nums . size ()- 1 ;         int index1=- 1 ,index2=- 1 ;         while (st<=en){             int mid = st + (en-st)/ 2 ;             if ( nums [mid]>target) en = mid- 1 ;             else if ( nums [mid]<target) st = mid+ 1 ;   ...

Lower bound: In binary search, the lower bound is the lowest position where the value could be inserted without breaking the ordering. In the C++ standard library, this bound will be represented by an iterator referencing the element before which the value could be inserted.  STL: int lower = lower_bound(vec.begin(), vec.end(), target); That function will return a int value, where we can put the target value with the compromising the sorted system. Upper bound: In binary search, the upper bound is the highest position where the value could be inserted without breaking the ordering. In the C++ standard library, this bound will be represented by an iterator referencing the element after which the value could be inserted.  STL: int upper = upper_bound(vec.begin(), vec.end(), target); That function will return a int value, where we can put the target value with the compromising the sorted system.

Binary search is a searching algorithm used in a sorted array by repeatedly dividing the search interval in half. The idea of binary search is to use the information that the array is sorted and reduce the time complexity to O(log N)¹.  Here's how it works: 1. Compare x with the middle element. 2. If x matches with the middle element, we return the mid index. 3. Else If x is greater than the mid element, then x can only lie in the right half subarray after the mid element. So we recur for the right half. 4. Else (x is smaller) recur for the left half. This process continues until the element is found or the subarray is empty. Look at the array, it is sorted and if we want to find 7 in this array easily by implementing binary search algorithm. We can find it in O(logn) time. While a linear search will take O(n) time which is very long time. So, if an array is sorted we always use Binary search. Algorithm: int main() {     optimize();     int arr[]= {1,4,5,8,10,26...