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

Constraints:

  • 1 <= nums.length <= 104
  • -104 < nums[i], target < 104
  • All the integers in nums are unique.
  • nums is sorted in ascending order.
Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main
    implicit none

    integer, parameter :: n = 6
    integer, dimension(n) :: nums = [-1, 0, 3, 5, 9, 12]
    integer :: target
    integer :: result

    ! Example 1
    target = 9
    result = search(nums, target)
    print '(A, I0)', 'Example 1: ', result

    ! Example 2
    target = 2
    result = search(nums, target)
    print '(A, I0)', 'Example 2: ', result

contains

    function search(nums, target) result(index)
        implicit none
        integer, dimension(:), intent(in) :: nums
        integer, intent(in) :: target
        integer :: index

        index = binary_search(nums, target, 1, size(nums))
    end function search

    recursive function binary_search(nums, target, left, right) result(index)
        implicit none
        integer, dimension(:), intent(in) :: nums
        integer, intent(in) :: target
        integer, value :: left, right
        integer :: mid

        if (left > right) then
            index = -1
            return
        end if

        mid = (left + right) / 2

        if (nums(mid) == target) then
            index = mid
        else if (nums(mid) < target) then
            index = binary_search(nums, target, mid + 1, right)
        else
            index = binary_search(nums, target, left, mid - 1)
        end if
    end function binary_search
end program main
❌ Compiled
❌ Executed
❌ Correct 
module binary_search

implicit none

contains

function search(nums, target) result(index)

integer, intent(in) :: nums(:)
integer, intent(in) :: target
integer :: index

index = -1

if (size(nums) == 0) then
    return
endif

call binary_search_recursive(nums, target, 1, size(nums), index)

end function search

recursive subroutine binary_search_recursive(nums, target, left, right, index)

integer, intent(in) :: nums(:)
integer, intent(in) :: target
integer, intent(in) :: left
integer, intent(in) :: right
integer, intent(out) :: index

integer :: mid

if (left > right) then
    return
endif

mid = (left + right) / 2

if (nums(mid) == target) then
    index = mid
    return
endif

if (nums(mid) < target) then
    call binary_search_recursive(nums, target, mid + 1, right, index)
else
    call binary_search_recursive(nums, target, left, mid - 1, index)
endif

end subroutine binary_search_recursive

end module binary_search

program test

use binary_search

implicit none

integer, parameter :: nums = [-1, 0, 3, 5, 9, 12]
integer :: target
integer :: index

target = 9
index = search(nums, target)
write (*,*) "Target: ", target, " Index: ", index

target = 2
index = search(nums, target)
write (*,*) "Target: ", target, " Index: ", index

end program test
🌐 Data from online sources 
def search(nums: List[int], target: int) -> int:
    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 -1

The algorithm implements a binary search, since the input array is sorted in ascending order. We start with two pointers, `left` and `right`, representing the beginning and the end of the search range, respectively. We then find the middle element of the array (or subarray) by calculating the average of `left` and `right` and round it down.

If the middle element matches the target, we return its index. If the middle element is smaller than the target, we set left to the next index (mid + 1). If the middle element is greater than the target, we set right to the previous index (mid - 1). We continue iterating until we find the target or the pointers cross (left > right), in which case we return -1 because the target is not in the array. The time complexity of this algorithm is O(log n).

🌐 Data from online sources 
int search(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 -1;
}

The algorithm implements a binary search, since the input array is sorted in ascending order. We start with two pointers, `left` and `right`, representing the beginning and the end of the search range, respectively. We then find the middle element of the array (or subarray) by calculating the average of `left` and `right` and round it down.

If the middle element matches the target, we return its index. If the middle element is smaller than the target, we set left to the next index (mid + 1). If the middle element is greater than the target, we set right to the previous index (mid - 1). We continue iterating until we find the target or the pointers cross (left > right), in which case we return -1 because the target is not in the array. The time complexity of this algorithm is O(log n).