Session 7: IL - Binary Search

Original Session

Date: 14 Nov 2024

Topic: Binary Search

1. Concept: Floor and Ceil
   1. floor, one less than the number
   2. ceil, one greater than the number.
      1. low will always ceil in the array.
      2. high is always floor in the array.

Programs

1. 35. Search Insert Position
   1. leetcode link

      public int searchInsert(int[] nums, int target) {
              
              int left = 0;
              int right = nums.length - 1;
              
              while (left <= right) {
      
                  int middle = (left + right) / 2;
      
                  if (nums[middle] == target) {
                      return middle;
                  }
      
                  if (target < nums[middle]) {
                      right = middle - 1;
                  } else {
                      left = middle + 1;
                  }
              }
      
              return right + 1;
          }

2. GFG find floor
   1. GFG link
   2. 
      
      

   static int findFloor(int[] nums, int target) {
           // write code here
           
           int left = 0;
           int right = nums.length - 1;
           
           while (left <= right) {
   
               int middle = (left + right) / 2;
   
               if (nums[middle] == target) {
                   return middle;
               }
   
               if (target < nums[middle]) {
                   right = middle - 1;
               } else {
                   left = middle + 1;
               }
           }
   
           return nums[right];
       }

3. 69. Sqrt(x)

   public int mySqrt(int x) {
           
           long low = 0;
           long right = x;
           long ans = 0;
   
           while (low <= right) {
   
               long mid = (low + right)/2;
   
               if (mid*mid <= x) {
                   ans = mid;
                   low = mid + 1;
               } else {
                   right = mid - 1;
               }
           }
   
           return (int)ans;
       }

4. 34. Find First and Last Position of Element in Sorted Array
   1. leetcode link

   public int[] searchRange(int[] nums, int target) {
           return new int[] {firstOccurence(nums, target), lastOccurence(nums, target)};
       }
   
       int firstOccurence(int[] nums, int target) {
   
           int left = 0;
           int right = nums.length - 1;
           int ans = -1;
           
           while (left <= right) {
   
               int middle = (left + right) / 2;
   
               if (nums[middle] == target) {
                   ans = middle;
                   right = middle - 1;
               } else if (target > nums[middle]) {
                   left = middle + 1;
               } else {
                   right = middle - 1;
               }
           }
   
           return ans;
       }
   
       int lastOccurence(int[] nums, int target) {
   
           int left = 0;
           int right = nums.length - 1;
           int ans = -1;
           
           while (left <= right) {
   
               int middle = (left + right) / 2;
   
               if (nums[middle] == target) {
                   ans = middle;
                   left = middle + 1;
               } else if (target > nums[middle]) {
                   left = middle + 1;
               } else {
                   right = middle - 1;
               }
           }
   
           return ans;
       }

5. 162. Find Peak Element
   1. leetcode link

   public int findPeakElement(int[] nums) {
           
           return findPeakElement2(nums);
       }
   	
   		// This solutin is not working
       public int findPeakElement1(int[] nums) {
           
           int n = nums.length;
           if (n==1) {
               return 0;
           }
   
           if (n==2) {
               if (nums[0] > nums[1]) {
                   return 0;
               }
               return 1;
           }
   
           if (nums[0] > nums[1] ) {
               return 0;
           }
   
           if (nums[n-1] > nums[n-2] ) {
               return n-1;
           }
   
           int low = 0;
           int high = n-1;
   
           while (low <= high) {
   
               int mid = (low+high)/2;
   
               if (nums[mid-1]<nums[mid] &&
                   nums[mid]>nums[mid+1]) {
                       return mid;
               }
   
               if (nums[mid] < nums[mid+1]) {
                   low = mid + 1;
               } else {
                   high = mid - 1;
               }
           }
   
           return -1;
       }
   
   		// This solution is working
       public int findPeakElement2(int[] nums) {
           int low = 0;
           int high = nums.length - 1;
   
           while (low < high) {
   
               int mid = (low+high)/2;
               if (nums[mid] > nums[mid+1]) {
                   high = mid;
               } else {
                   low = mid + 1;
               }
           }
           return low;
       }