Binary Search Recursive Approach in DSA Go - Build from Scratch

Binary Search Recursive Approach

📖 Scenario: You have a sorted list of book IDs in a library system. You want to find if a specific book ID exists using a fast method.

🎯 Goal: Build a recursive binary search function in Go to find a book ID in a sorted list.

📋 What You'll Learn

Create a sorted slice of integers called bookIDs with exact values

Create two integer variables left and right for the search range

Write a recursive function binarySearch that takes bookIDs, left, right, and target as parameters

The function returns the index of target if found, or -1 if not found

Call the function with the correct parameters and print the result

💡 Why This Matters

🌍 Real World

Binary search is used in many software systems to quickly find data in sorted lists, like searching for a book ID in a library database.

💼 Career

Understanding binary search helps in roles involving data processing, software development, and algorithm optimization.

1

Create the sorted list of book IDs

Create a slice of integers called bookIDs with these exact values: 2, 5, 8, 12, 16, 23, 38, 56, 72, 91

DSA Go

bookIDs := []int{2, 5, 8, 12, 16, 23, 38, 56, 72, 91}
// Your code here

Hint

Use a slice literal with the exact numbers in order.

2

Set the initial search range variables

Create two integer variables called left and right. Set left to 0 and right to the last index of bookIDs (which is 9).

DSA Go

package main

import "fmt"

func main() {
    bookIDs := []int{2, 5, 8, 12, 16, 23, 38, 56, 72, 91}
    left := 0
    right := 9
    // Your code here
}

Hint

Remember the last index is length minus one.

3

Write the recursive binary search function

Write a recursive function called binarySearch that takes parameters bookIDs []int, left int, right int, and target int. It should return an int. Implement the binary search logic: if left is greater than right, return -1. Otherwise, find the middle index, compare bookIDs[middle] with target, and recursively search the left or right half accordingly.

DSA Go

package main

import "fmt"

func main() {
    bookIDs := []int{2, 5, 8, 12, 16, 23, 38, 56, 72, 91}
    left := 0
    right := 9
}

func binarySearch(bookIDs []int, left int, right int, target int) int {
    // Your code here
}

Hint

Use the middle index formula and recursive calls for left and right halves.

4

Call the function and print the result

Call binarySearch with bookIDs, left, right, and target set to 23. Store the result in a variable called index. Then print index.

DSA Go

package main

import "fmt"

func main() {
    bookIDs := []int{2, 5, 8, 12, 16, 23, 38, 56, 72, 91}
    left := 0
    right := 9
    index := binarySearch(bookIDs, left, right, 23)
    // Your code here
}

func binarySearch(bookIDs []int, left int, right int, target int) int {
    if left > right {
        return -1
    }
    middle := left + (right-left)/2
    if bookIDs[middle] == target {
        return middle
    } else if bookIDs[middle] > target {
        return binarySearch(bookIDs, left, middle-1, target)
    } else {
        return binarySearch(bookIDs, middle+1, right, target)
    }
}

Hint

The index of 23 in the list is 5. Use fmt.Println to print the index.