2023-04-01 Daily Challenge

Posted on:
Posted modified:
In: DailyChallenge

Today I have done leetcode's April LeetCoding Challenge with cpp.

April LeetCoding Challenge 1

Description

Binary Search

Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.

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

 

Example 1:

Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4

Example 2:

Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
Explanation: 2 does not exist in nums so return -1

 

Constraints:

  • 1 <= nums.length <= 104
  • -104 < nums[i], target < 104
  • All the integers in nums are unique.
  • nums is sorted in ascending order.

Solution

auto speedup = [](){
  cin.tie(nullptr);
  cout.tie(nullptr);
  ios::sync_with_stdio(false);
  return 0;
}();
class Solution {
public:
  int search(vector<int>& nums, int target) {
    int begin = 0, end = nums.size()-1;
    while(begin < end) {
      int mid = (begin + end) >> 1;
      if(nums[mid] >= target) {
        end = mid;
      } else {
        begin = mid+1;
      }
    }
    return nums[begin]==target?begin:-1;
  }
};

// Accepted
// 47/47 cases passed (28 ms)
// Your runtime beats 98.7 % of cpp submissions
// Your memory usage beats 13.43 % of cpp submissions (27.7 MB)
Algorithm