Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
You must write an algorithm with O(log n) runtime complexity.
Example 1:
Input: nums = [1,3,5,6], target = 5 Output: 2
Example 2:
Input: nums = [1,3,5,6], target = 2 Output: 1
Example 3:
Input: nums = [1,3,5,6], target = 7 Output: 4
Constraints:
1 <= nums.length <= 104-104 <= nums[i] <= 104nums contains distinct values sorted in ascending order.-104 <= target <= 104program binary_search
implicit none
integer, parameter :: n = 4
integer, dimension(n) :: nums = (/ 1, 3, 5, 6 /), target
integer :: i, j, k, l, m
! Example 1
target = 5
call binary_search_example(nums, target)
! Example 2
target = 2
call binary_search_example(nums, target)
! Example 3
target = 7
call binary_search_example(nums, target)
contains
subroutine binary_search_example(nums, target)
implicit none
integer, intent(in) :: nums(:), target
integer :: i, j, k, l, m
i = 1
j = size(nums)
do while (i < j)
k = (i + j)/2
if (nums(k) == target) then
print '(A,I0)', 'Target found at index ', k
return
else if (nums(k) < target) then
i = k + 1
else
j = k
end if
end do
if (i == j) then
print '(A,I0)', 'Target not found. Insertion index: ', i
else
print '(A,I0)', 'Target not found. Insertion index: ', i - 1
end if
end subroutine binary_search_example
end program binary_searchtemp.f95:10:37:
10 | call binary_search_example(nums, target)
| 1
Error: Rank mismatch in argument ‘target’ at (1) (scalar and rank-1)
temp.f95:14:37:
14 | call binary_search_example(nums, target)
| 1
Error: Rank mismatch in argument ‘target’ at (1) (scalar and rank-1)
temp.f95:18:37:
18 | call binary_search_example(nums, target)
| 1
Error: Rank mismatch in argument ‘target’ at (1) (scalar and rank-1)
module binary_search
implicit none
private
public :: binary_search_index
contains
function binary_search_index(nums, target) result(index)
integer, intent(in) :: nums(:)
integer, intent(in) :: target
integer :: index
index = binary_search_index_recursive(nums, target, 1, size(nums))
end function binary_search_index
recursive function binary_search_index_recursive(nums, target, left, right) result(index)
integer, intent(in) :: nums(:)
integer, intent(in) :: target
integer, intent(in) :: left
integer, intent(in) :: right
integer :: middle
integer :: index
if (left > right) then
index = -1
return
end if
middle = (left + right) / 2
if (nums(middle) == target) then
index = middle
else if (nums(middle) < target) then
index = binary_search_index_recursive(nums, target, middle + 1, right)
else
index = binary_search_index_recursive(nums, target, left, middle - 1)
end if
end function binary_search_index_recursive
end module binary_search
! Test the binary search module
program test_binary_search
use binary_search
implicit none
integer, parameter :: nums = [1, 3, 5, 6]
integer :: target
integer :: index
! Test case 1: target found
target = 5
index = binary_search_index(nums, target)
write (*,*) 'Target found at index: ', index
! Test case 2: target not found
target = 2
index = binary_search_index(nums, target)
write (*,*) 'Target not found. Insertion index: ', index
! Test case 3: target greater than all elements
target = 7
index = binary_search_index(nums, target)
write (*,*) 'Target greater than all elements. Insertion index: ', index
end program test_binary_search
temp.f95:47:26:
47 | integer, parameter :: nums = [1, 3, 5, 6]
| 1
Error: Incompatible ranks 0 and 1 in assignment at (1)
temp.f95:53:32:
53 | index = binary_search_index(nums, target)
| 1
Error: Symbol ‘nums’ at (1) has no IMPLICIT type
def searchInsert(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] == target:
return mid
if nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return left
The given problem requires a binary search algorithm. We define two pointers, left and right, initially set to the first and last index of the array. We then enter a loop that continues as long as left is less than or equal to right. Inside the loop, we calculate the middle index, mid, as the average of left and right. If the value at this middle index is equal to the target value, we return the middle index. If the middle value is less than the target value, we set left to mid + 1, meaning we search the right half of the remaining array. If the middle value is greater than the target value, we set the right to mid - 1, meaning we search the left half of the remaining array. After the loop, if the target value is not found, we return the value of the left pointer, which represents the index where the target value should be inserted.
int searchInsert(vector<int>& nums, int target) {
int left = 0, right = nums.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) return mid;
if (nums[mid] < target) left = mid + 1;
else right = mid - 1;
}
return left;
}
The given problem requires a binary search algorithm. We define two pointers, left and right, initially set to the first and last index of the array. We then enter a loop that continues as long as left is less than or equal to right. Inside the loop, we calculate the middle index, mid, as the average of left and right. If the value at this middle index is equal to the target value, we return the middle index. If the middle value is less than the target value, we set left to mid + 1, meaning we search the right half of the remaining array. If the middle value is greater than the target value, we set the right to mid - 1, meaning we search the left half of the remaining array. After the loop, if the target value is not found, we return the value of the left pointer, which represents the index where the target value should be inserted.