Binary Search Algorithm in 100 Seconds

we will try to solve some problems on binary search so be ready.🥶

Binary search in 4 minutes

704. Binary Search #Easy #leet_code_Q5 #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

share ur solution on the comment section or in the group.

``` class Solution:
def search(self, nums: List[int], target: int) -> int:
left = 0
right = len(nums)-1
while(left<=right):
mid = (left+right)//2
if nums[mid] == target:
return mid
elif nums[mid] >target:
right = mid -1
else:
left = mid+1
return -1```

answer:

744. find the smallest that greater than the target letter #binary_search #leet_code_Q6 #Easy You are given an array of characters letters that is sorted in non-decreasing order, and a character target. There are at least two different characters in letters.

Return the smallest character in letters that is lexicographically greater than target. If such a character does not exist, return the first character in letters.

Example 1:

Input: letters = ["c","f","j"], target = "a"
Output: "c"
Explanation: The smallest character that is lexicographically greater than 'a' in letters is 'c'.
Example 2:

Input: letters = ["c","f","j"], target = "c"
Output: "f"
Explanation: The smallest character that is lexicographically greater than 'c' in letters is 'f'.
Example 3:

Input: letters = ["x","x","y","y"], target = "z"
Output: "x"
Explanation: There are no characters in letters that is lexicographically greater than 'z' so we return letters[0]

Constraints:

2 <= letters.length <= 104
letters[i] is a lowercase English letter.
letters is sorted in non-decreasing order.
letters contains at least two different characters.
target is a lowercase English letter.

answer:

class Solution:
def nextGreatestLetter(self, letters: List[str], target: str) -> str:
left = 0
right = len(letters)-1
while(left<=right):
mid = (left+right)//2
if(letters[mid] > target )and (letters[mid-1] <= target or mid==left):
return letters[mid]
elif letters[mid] > target:
right = mid -1
else:
left = mid +1
return letters[0]

let's submit our answer:

it's 91% faster.😎

የማብድ ቢመስለኝ ፣ ድንገት አንቺን ሳጣ
አረቄ ቤት ሔጄ ፣ አረቄ ስጠጣ
አንድ ግጥም ሰማሁ
ፍቅርሽን ከልቤ ፣ ነቅሎ የሚያወጣ፡፡
ያውም መንገድ በሚል...
ለመንገደኛ ሰው ፣ ሰካራም የፃፈው
እዛ ጋ ቁጭ ብሎ...
"ከዳችኝ" እያለ ፣ የሚለፈልፈው
መንገድ የሚል ግጥሙ ፣ጆሮዬን ገረፈው፡፡
ጆሮዬ ሲገረፍ ፣
ጠባሳ ጣለብኝ ፣ ግጥሙን እንዳልረሳ
"መንገድ አያደርስም
መንገድ አይመልስም ፣ እግር ካልተነሳ!!!"
እያለ ይገጥማል...
ደጋግሞ ደጋግሞ ፣ ሌላ አይናገርም
እሱም ልክ እንደኔ ...
አንዷን በመሔዷ ፣ ሳያጣት አይቀርም፡፡
ብቻ ሰክሪያለሁ
ለመንገደኛ ሴት ፣
የተፃፈ ግጥምን ፣ ጆሮዬ ያደሞጣል
መሔድሽን ያየ
እንደሌሌሽኝ ሲያውቅ ፣ ሊኖረኝ ይመጣል
ይህ ነው መንገድ ማለት!
የሰካራም ግጥምን ሰክሬ ስረዳው
ማፍቀረ ሳይሆን ለኔ ፣ መርሳት ነው ሚጎዳው!!!

ሰለወደድኩት ነው

let's takcle leet code medium question for the first time

#binary_search #Medium #leet_code_Q7 852. Peak Index in a Mountain Array

An array arr is a mountain if the following properties hold:

arr.length >= 3
There exists some i with 0 < i < arr.length - 1 such that:
arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
arr[i] > arr[i + 1] > ... > arr[arr.length - 1]
Given a mountain array arr, return the index i such that arr[0] < arr[1] < ... < arr[i - 1] < arr[i] > arr[i + 1] > ... > arr[arr.length - 1].

You must solve it in O(log(arr.length)) time complexity.

Example 1:

Input: arr = [0,1,0]
Output: 1
Example 2:

Input: arr = [0,2,1,0]
Output: 1
Example 3:

Input: arr = [0,10,5,2]
Output: 1

Constraints:

3 <= arr.length <= 105
0 <= arr[i] <= 106
arr is guaranteed to be a mountain array.

How do we solve this? Any ideas?