✅ Binary Search (Important)

Most used searching technique in interviews.

Learn:

• Basic binary search on sorted array

• Lower bound / Upper bound concepts

• Handling integer overflow (mid = low + (high-low)/2)

• Searching ranges

• Binary search on answers (Advanced)

You must master:

• Search in rotated sorted array

• First/last occurrence

• Kth element problems

• Peak element

• Binary search on monotonic functions

🔥 Binary Search on Answer (Advanced)

Used when:

• Search space is monotonic

• You cannot directly see the sorted array, but decisions are monotonic

Examples:

• Allocate books

• Aggressive cows

• Minimum days to make bouquets

• Koko eating bananas

📝 Must Do Practice Problems

🔹 Level 1 – Easy

1. Leetcode 704. Binary Search

Solution

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int n = nums.size();
        int left = 0, right = n-1;
        int mid;
        while(left <= right) {
            mid = left + (right - left)/2;
            if(nums[mid] > target) right = mid - 1;
            else if(nums[mid] < target) left = mid + 1;
            else return mid;
        }
        return -1;
    }
};

1. Floor/Ceil of an Element in a Sorted Array - Approach

2. Leetcode 35. Search Insert Position - My Approach

3. Leetcode 744. Find Smallest Letter Greater Than Target

   • This is similar to finding Ceil of an element in a Sorted Array.

class Solution {
public:
    char nextGreatestLetter(vector<char>& letters, char target) {
        int n = letters.size();
        int l = 0, r = n-1, mid, ans = 0;
        while(l <= r) {
            mid = l + (r - l)/2;
            if(letters[mid] > target) {
                ans = mid;
                r = mid - 1;
            } else if(letters[mid] <= target) {
                l = mid + 1;
            }
        }
        return letters[ans];
    }
};

1. Leetcode 169. Majority Element - My Approach & Leetcode Solution link

🔹 Level 2 – Medium

1. Leetcode 34. Find First and Last Position of Element in Sorted Array - My Approach & Leetcode Solution link

2. Leetcode 540. Single Element in a Sorted Array - My Approach & Leetcode Solution link

3. Rotation Count in a Rotated Sorted Array - Click for My Approach

   Click here for Solution

4. Leetcode 153. Find Minimum in Rotated Sorted Array - My Approach & Leetcode Solution link

   This problem is exactly same as the above problem 3. Rotation Count in a Rotated Sorted Array

5. Leetcode 33. Search in Rotated Sorted Array - My Approach & Leetcode Solution link

   This problem is also the modified version of the previous problem 4 and hence problem 3.

6. Find Position of an Element in a Sorted Array of Infinite Numbers - Click here for my Approach

7. Index of first 1 in an infinite binary sorted array - Click here for my Approach

   Approach for this problem is similar to the previous problem number 6.

   • First find out the Bound where first time 1 can appear (say [l, r]).
   • Now find the occurrence of first 1 in [l, r].

8. Leetcode 162. Find Peak Element - My Approach & Leetcode Solution link

9. Leetcode 852. Peak Index in a Mountain Array - My Approach & Leetcode Solution link

10. Search in a row wise and column wise sorted matrix - **My Approach and Solution

11. Leetcode 74. Search a 2D Matrix - My Approach & Leetcode Solution link

12. Allocate Minimum Pages - My Approach and Solution

    • Binary search on value

13. Leetcode 875. Koko Eating Bananas - My Approach & Leetcode Solution link

    • For example visuals CLICK HERE
    • Binary search on value

14. Leetcode 981. Time Based Key-Value Store - My Approach & Leetcode Solution link

🔹 Level 3 – Hard

1. Leetcode 1095. Find in Mountain Array - My Approach & Leetcode Solution link

2. Leetcode 4. Median of Two Sorted Arrays - My Approach & Leetcode Solution link

   • For visual examples Click Here