Find the Index of a Target in a Sorted Array of Distinct Integers
Company: Visa
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Given an array `nums` of distinct integers sorted in strictly increasing order and an integer `target`, return the position of `target` in `nums`. If `target` is not present, return `-1`.
### Function Signature
```python
def find_target_index(nums: list[int], target: int) -> int:
```
### Rules
- Positions are 0-based: the first element of `nums` is at index 0.
- Because the values in `nums` are distinct, `target` appears at most once, so the returned index is unique.
- Return `-1` if and only if `target` does not occur in `nums`.
- Do not modify `nums`.
- The algorithm must run in $O(\log n)$ time, where $n$ is the length of `nums`.
### Constraints
- `1 <= len(nums) <= 10^4`
- `-10^4 < nums[i] < 10^4` for every index `i`
- `-10^4 < target < 10^4`
- `nums[i] < nums[i + 1]` for every `0 <= i < len(nums) - 1` (strictly increasing, so there are no duplicates)
- All values are well within the 32-bit signed integer range.
### Examples
**Example 1**
```text
Input: nums = [-7, -2, 0, 4, 11, 15], target = 4
Output: 3
```
`nums[3]` is 4.
**Example 2**
```text
Input: nums = [-7, -2, 0, 4, 11, 15], target = 5
Output: -1
```
5 would fall between 4 and 11, but it is not in the array.
**Example 3**
```text
Input: nums = [8], target = 8
Output: 0
```
The only element is the target.
Overview: Practice locating a target value in a strictly increasing array of distinct integers, returning its zero-based index or -1 when it is absent. The task checks logarithmic-time search over sorted data, precise loop boundaries, and correct handling of single-element arrays and values that fall between or outside the stored elements.
Read the full Visa Software Engineer interview experience this question came from
Community answers
Answer by ss007
def findnum(nums, target):
if nums is None:
return -1
# use binary search as it is a sorted array
lenNums = lens(nums)
mid = (lenNums-1)/2 + 1
i = 0
j = lenNums
while ( i < j):
if target == nums [mid]:
return mid
elif target < nums[mid]:
j = mid -1
else:
i = mid + 1
return -1 # target does not exist in the nuts
Answer by pdawn
It's a simple binary search problem
// code in java
int find_target_index(int[] nums, int target){
int low = 0;
int high = nums.length-1;
while(low<=high){
int mid = (low+high)/2;
if(nums[mid]>target){
high = mid-1;
}else if(nums[mid]<target){
low=mid+1;
}else{
return mid;
}
}
return -1;
}