[!NOTE] we use binary search in sorted arrays. if we get problem statement with sorted array try binary search first.
Q.1 ceiling of a given number
ceiling of no is smallest ele in arr greater ot == target arr = [2,3,4,5,9,14,16,18], target = 14 if target = 14 then ceiling = 14 ceiling(arr,target=15) = 16
Q.2 Floor of a number
Code
Q.3 Find Smallest letter greater than target [ leetcode : 744 ]
- Exact same approach for cieling of the number
- ignore the target = what are looking for.
- wrapping of later eg: arr = [‘c’,’d’,‘f’,‘j’] , target = ‘j’ output = c we will use modulo (%)
- condition violeted : start = end + 1 ==> length of array = N
4. Find First and Last Position of Element in Sorted Array
Example 1: Input: nums = [5,7,7,8,8,10], target = 8 Output: [3,4]
Example 2: Input: nums = [5,7,7,8,8,10], target = 6 Output: [-1,-1]
Example 3: Input: nums = [], target = 0 Output: [-1,-1]
5. Find position of an element in a sorted array of infiniate numbers. (amazon interview question)
try not to use array.length in infinite array
https://youtu.be/W9QJ8HaRvJQ?list=PL9gnSGHSqcnr_DxHsP7AW9ftq0AtAyYqJ&t=6656
traverse through chunks
Doubling the size of chuck
6. leetcode 852 peak index in a mountain Array
also known as biotonic arrray = {1,2,3,4,3,2,1}
find peak in mountain array try to solve this question with linear search
but here i am using binary search to solve this
it is the sorted array it is sorted in 3 halfs (first asending 2nd decenting)
7. leetcode 1095 find in mountain array
Search in mountain
code for this will try later
8. Search in a Rotated Sorted Array (LeetCode 33)
distinct value (no dublicates)
2 approaches
case 1:
remember pivot is the largest number
- find pivot
- search in first half (simple binary search) [o,pivot]
- otherwise, search in second half [pivot + 1, end ]
case 2:
if mid ele < (mid - 1) ele , so my ans is (mid - 1)
case 3:
start ele > mid - element
case 4
Code : (duplicate value rotation code is also included)
Q.9 rotation count
ans = pivot +1