Cant figure out why the heck is this incorrect implementation of Binary Search in go. Input is ([]int{-1, 0, 3, 5, 9, 12}, 9)

func Search(nums []int, target int) int {

    mid := len(nums) / 2

    if nums[mid] == target {
        return mid
    }
    if len(nums) >= 1 {
        if nums[mid] < target {
            return Search(nums[mid 1:], target)
        } else {
            return Search(nums[:mid], target)
        }
    }

    return -1
}

CodePudding user response：

Binary Search

func Search(nums []int, target int) int {

    mid := len(nums) / 2

    if nums[mid] == target {
        return mid
    }
    if len(nums) >= 1 {
        if nums[mid] < target {
            return Search(nums[mid:], target)   mid
        } else {
            return Search(nums[:mid], target)
        }
    }

    return -1
}

The one line that was changed is the following:

return Search(nums[mid:], target) mid

CodePudding user response：

Lets say, your slice is nums=[5,12,17,20,30,39,55,67]. Your target number is 55. When you make a recursive call on the right side of the array in the line return Search(nums[mid:], target), the new slice is nums=[30,39,55,67]. The index of 55 was 6 in the original slice but in the new slice, it is 2. That is why you are not getting the correct answer.

When you make a new slice from an existing slice, the index of the elements does not reflect the old slice. To make this up you need to add the current mid when you are selecting the right side of the slice for binary search.