Question 5
Question 5: Ascending Order of the Array
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:
C++
Java
Python
C++
Run
#include <bits/stdc++.h> using namespace std; int search(vector& nums, int target) { int left = 0; int right = nums.size() - 1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] == target) { return mid; } else if (nums[mid] < target) { left = mid + 1; } else { right = mid - 1; } } return -1; // Target not found } int main() { int n, target; cout << "Enter the number of elements: "; cin >> n; vector nums(n); cout << "Enter the sorted elements: "; for (int i = 0; i < n; i++) { cin >> nums[i]; } cout << "Enter the target: "; cin >> target; int index = search(nums, target); if (index != -1) { cout << "Target found at index: " << index << endl; } else { cout << "Target not found in the array." << endl; } return 0; }
Java
Run
import java.util.Scanner;
class Main {
public static int search(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1; // Target not found
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("Enter the number of elements: ");
int n = sc.nextInt();
int[] nums = new int[n];
System.out.print("Enter the sorted elements: ");
for (int i = 0; i < n; i++) {
nums[i] = sc.nextInt();
}
System.out.print("Enter the target: ");
int target = sc.nextInt();
int index = search(nums, target);
if (index != -1) {
System.out.println("Target found at index: " + index);
} else {
System.out.println("Target not found in the array.");
}
}
}
Python
Run
def search(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1 # Target not found
n = int(input("Enter the number of elements: "))
nums = list(map(int, input("Enter the sorted elements: ").split()))
target = int(input("Enter the target: "))
index = search(nums, target)
if index != -1:
print("Target found at index:", index)
else:
print("Target not found in the array.")
