# Find Smallest Letter Greater Than Target

Given a characters array `letters`

that is sorted in **non-decreasing** order and a character `target`

, return *the smallest character in the array that is larger than *`target`

.

**Note** that the letters wrap around.

- For example, if
`target == 'z'`

and`letters == ['a', 'b']`

, the answer is`'a'`

.

**Example 1:**

**Input:** letters = ["c","f","j"], target = "a"

**Output:** "c"

**Example 2:**

**Input:** letters = ["c","f","j"], target = "c"

**Output:** "f"

**Example 3:**

**Input:** letters = ["c","f","j"], target = "d"

**Output:** "f"

**Example 4:**

**Input:** letters = ["c","f","j"], target = "g"

**Output:** "j"

**Example 5:**

**Input:** letters = ["c","f","j"], target = "j"

**Output:** "c"

`Constraints:`

`2 <= letters.length <= 104`

Approach 1 :

Iterate through array on finding the first letter greater than the target , return the same. Else if you can’t find then return the first number in the array

Solution:

pseudo code

for i in letters:

if(i>target):

found i

break the loop

if not found

found letters[0]

Time :O(n)

Space O(1)

Approach 2 :

Binary search

Since the array is sorted, we can employ the binary search .Set low to first index position , high to last index position. If the mid element is less than the target then low is set to mid+1

else if mid element greater than the target , high(h) set to mid-1, this mid element.

Solution:

` low=0`

high=len(letters)-1

res=letters[0]

while(low<=high):

mid=(low+high)//2

if(ord(letters[mid])<=ord(target)):

low=mid+1

elif(ord(letters[mid])>ord(target)):

res=letters[mid]

high=mid-1

print res

Time :O(log(n))

Space :O(1)