Session 8: Binary Search

Original Session

Date: 16 Nov 2024

Topic: Binary Search

1. Concept: In rotated sorted array, Any one half is always sorted.

2. Concept: Minimum element in rotated array is always present in unsorted part.

3. Concept: In case of duplicates in sorted array, think about moving low and high to exclude duplicates.

Programs

1. 33. Search in Rotated Sorted Array
   1. leetcode here

      public int search(int[] nums, int target) {
      
              int low = 0;
              int high = nums.length - 1;
      
              while (low <= high) {
      
                  int mid = (low + high) / 2;
      
                  if (nums[mid] == target) {
                      return mid;
                  }
      
                  // If first part is sorted.
                  if (nums[low] <= nums[mid]) {
      
                      // key lies in this part
                      if (nums[low] <= target && target < nums[mid]) {
                          high = mid - 1;
                      } else {
                          low = mid + 1;
                      }
                  } else {
                      // target is in this part
      
                      if (nums[mid] < target && target <= nums[high]) {
                          low = mid + 1;
                      } else {
                          high = mid - 1;
                      }
                  }
              }
      
              return -1;
          }

2. 81. Search in Rotated Sorted Array II
   1. leetcode here

   public boolean search(int[] nums, int target) {
           
           int low = 0;
           int high = nums.length - 1;
   
           while (low <= high) {
   
               int mid = (low + high) / 2;
   
               if (nums[mid] == target) {
                   return true;
               }
   
               
               if (nums[low] == nums[mid] && nums[high] == nums[mid]) {
                   low ++;
                   high --;
               }else if (nums[low] <= nums[mid]) {
   								// If first part is sorted.
                   // key lies in this part
                   if (nums[low] <= target && target < nums[mid]) {
                       high = mid - 1;
                   } else {
                       low = mid + 1;
                   }
               } else {
                   // target is in this part
   
                   if (nums[mid] < target && target <= nums[high]) {
                       low = mid + 1;
                   } else {
                       high = mid - 1;
                   }
               }
           }
   
           return false;
       }

3. 153. Find Minimum in Rotated Sorted Array
   1. leetcode here

   public int findMin(int[] nums) {
           
           int low = 0;
           int high = nums.length - 1;
   
           while (low < high) {
   
               int mid = (low + high) / 2;
   
               if (nums[mid] > nums[high]) {
                   low = mid + 1;
               } else {
                   high = mid;
               }
           }
   
           return nums[low];
       }

4. 154. Find Minimum in Rotated Sorted Array II
   1. leetcode here

   public int findMin(int[] nums) {
           
           int low = 0;
           int high = nums.length - 1;
   
           while (low < high) {
   
               int mid = (low + high) / 2;
   
               if (nums[mid] == nums[high]) {
                   high --;
               }else if (nums[mid] > nums[high]) {
                   low = mid + 1;
               } else {
                   high = mid;
               }
           }
   
           return nums[low];
       }