Program for Binary Search in a sorted array

Overview

Idea is to do a binary search of a given target element in an input array. If the target element is present then output the index. If the output element is not present then output -1.

Expected Time Complexity if O(logn)

Example 1

Input: [1, 4, 5, 6]
Target Element: 4
Output: 1

Target element 4 is present at index 1

Example 2

Input: [1, 2, 3]
Target Element: 4
Output: -1

Target element 4 is present at index 1

Program

package main

import "fmt"

func search(nums []int, target int) int {
	return binarySearch(nums, 0, len(nums)-1, target)
}

func binarySearch(nums []int, start, end, target int) int {
	if start > end {
		return -1
	}
	mid := (start + end) / 2

	if nums[mid] == target {
		return mid
	}

	if target < nums[mid] {
		return binarySearch(nums, start, mid-1, target)
	} else {
		return binarySearch(nums, mid+1, end, target)
	}
}

func main() {
	index := search([]int{1, 4, 5, 6}, 4)
	fmt.Println(index)

	index = search([]int{1, 2, 3, 6}, 4)
	fmt.Println(index)
}

Output

1
-1

Also, check out our system design tutorial series here – System Design Tutorial Series