Session 6: BitManipulation & Searching

Original Session

Date: 10 Nov 2024

• Topic: Searching
  • Concept Searching.
    • Sorted Array, then binary search.
  • Concept: Time Complexity logN
    • N(1/2 + 1/4 + 1/8 + 1/16 + …) expansion of log.

1. 704. Binary Search
   1. leetcode link

   public int search(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 -1;
       }