Skip to main content

Day 21: Find First and Last Position of Element in Sorted Array: Binary Search - leetcode - Python3

 


Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.

If target is not found in the array, return [-1, -1].

You must write an algorithm with O(log n) runtime complexity.

Example 1:

Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]

Example 2:

Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]

Example 3:

Input: nums = [], target = 0
Output: [-1,-1]

Constraints:

  • 0 <= nums.length <= 105
  • -109 <= nums[i] <= 109
  • nums is a non-decreasing array.
  • -109 <= target <= 109
SOLUTION

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        left = self.search(nums, target, True)
        right = self.search(nums, target, False)
        return [left, right]

    def search(self, nums, target, leftBias):
        l, r = 0, len(nums)-1
        i = -1

        while l <= r:
            mid: int = (l+r)//2
            if target > nums[mid]:
                l = mid+1
            elif target < nums[mid]:
                r = mid-1
            else:
                i = mid
                if leftBias:
                    r = mid-1
                else:
                    l = mid+1
        return i

Time Complexity: O(log n)

Space Complexity:O(1)

How it works:

The searchRange function first calls the search function to find the index of the first occurrence of target in nums. The search function works by using a binary search algorithm. A binary search algorithm works by repeatedly dividing the search space in half and then searching the half that is more likely to contain the target. The search function starts by setting the left and right pointers to the beginning and end of the search space, respectively. The function then repeatedly does the following:

  1. Calculate the midpoint of the search space.
  2. Compare the target to the element at the midpoint.
  3. If the target is equal to the element at the midpoint, return the midpoint index.
  4. If the target is less than the element at the midpoint, set the right pointer to the midpoint minus 1.
  5. If the target is greater than the element at the midpoint, set the left pointer to the midpoint plus 1.

The search function continues to do this until the left pointer is greater than or equal to the right pointer. If the left pointer is greater than or equal to the right pointer, then the target is not found in the search space.

Once the search function has found the index of the first occurrence of target in nums, the searchRange function then calls the search function again to find the index of the last occurrence of target in nums. The search function is called with the leftBias argument set to False. This tells the search function to search for the last occurrence of target in nums.

The searchRange function then returns a list containing the index of the first occurrence of target in nums and the index of the last occurrence of target in nums.

Comments

Popular posts from this blog

Bug Boundy Methodology, Tools & Resources

Start by defining a clear objective, such as exploiting a remote code execution (RCE) vulnerability or bypassing authentication on your target. Then, consider how you can achieve this goal using various attack vectors like XSS, SSRF, or others - these are simply tools to help you reach your objective. Use the target as how a normal user would, while browsing keep these questions in mind: 1)How does the app pass data? 2)How/where does the app talk about users? 3)Does the app have multi-tenancy or user levels? 4)Does the app have a unique threat model? 5)Has there been past security research & vulnerabilities? 6)How does the app handle XSS, CSRF, and code injection?

Install & set up mitmweb or mitmproxy in Linux

Step 1: Go to the mitmproxy page and download the binaries. Step 2: Install the downloaded tar file with the command " tar -xzf <filename>.tar.gz " Step 3: In the FoxyProxy add the proxy 127.0.0.1:8080  and turn it on. Step 4 : In the terminal run command " ./mitmweb " Step 5: Go to the page  http://mitm.it/   and download the mitmproxy's Certificate. Step 6: If you downloaded the certificate for Firefox, then go to " settings -> Privacy & Security -> Click View Certificates -> Click  Import ", then import the certificate.  Step 7: Now you are ready to capture the web traffic. Step 8 : In terminal run " ./mitmweb"

Making CHIP-8 emulator in C

  Chip8 doc link | Components | Opcode Table GitHub - AdithyakrishnaV/Chip8_Emulator--Interpreter Contribute to AdithyakrishnaV/Chip8_Emulator--Interpreter development by creating an account on GitHub. github.com CHIP-8 programs are binary files, and your emulator must read them and operate on the bytes. You will also need a way to draw graphics to the screen and read keypresses. Many graphical libraries can do this for you or use something like SDL directly. CHIP-8 components Display 64 pixels wide and 32 pixels tall. Each pixel is a boolean value, or a bit; can be on or off (“off” pixel was just black, and “on” was white). We’ll use SDL for rendering: SDL initialization Not initialize:- returns -1  Error message is stored in SDL_GetError Initializing SDL if (SDL_Init(SDL_INIT_VIDEO)!= 0 ){ printf ( "SDL not initialized,%s\n" , SDL_GetError); exit (- 1 ); } Initialize display SDL_Window * window = SDL_CreateWindow ( "chip8" , SDL_WINDOWPOS_CENTERED , SDL_...