Simple application of Binary Search
  1. Binary Search to find X in sorted array
  2. Implement Lower Bound
  3. Implement Upper Bound
  4. Search Insert Position
  5. Floor/Ceil in Sorted Array
  6. Find First and Last Position of Element in Sorted Array
  7. Count Occurrences in Sorted Array

​
Binary Search on Unsorted Array

​
1. Rotation Point in rotated Sorted Array

Even though the array is not sorted end-to-end, you can binary search for the minimum element (i.e., the rotation point) Binary search on a rotated sorted array is a modification of the standard binary search algorithm. The key idea is to identify the sorted half of the array(eliminating the other half) in each iteration and then determine if the target element lies within that sorted half. Here’s why we need to check which half is sorted:
  1. Binary Search Requirements: Binary search works on sorted arrays because it can make decisions about which half to search based on the middle element In a normal sorted array, if target > nums[mid], we know it must be in the right half If target < nums[mid], we know it must be in the left half
  2. In Rotated Arrays: We can’t make these simple decisions because the array is not fully sorted However, we know that at least one half (left or right of mid) must be sorted By checking nums[left] <= nums[mid], we can determine if the left half is sorted If left half is sorted, we can make a decision about searching in that half If left half is not sorted, then the right half must be sorted
Problems:
  1. Search in Rotated Sorted Array