Binary Search implementation in golang recursive

Binary Search is most used search algorithm, for daily problem solving and programming interview. In today post we are going to implement binary search using golang.

Binary search is a search algorithm which work on sorted list or array and find the position of target value or return boolean value based on existing of target value inside the list.

Binary search runs in logarithmic time in the worst case, making   O(log n) comparisons, where n is the number of elements in the array.

 

Lets Follow the steps for implementation:

1. Set startIndex to 0 and lastIndex to n-1 where n is length of array.
2. if startIndex > lastIndex terminate the search break the recursion.
3. set middleIndex = (L+R)/2
4. if arr[middleIndex] < targetNumber set startIndex = middleIndex + 1 and go to step 2
5. if arr[middleIndex] > targetNumber set lastIndex = middleIndex - 1 and go to step 2.
6. if arr[middleIndex] == targetNumber return middleIndex

Let implement above algo to code.

We are going to use Go or golang to implement this solution:

 

package main

import "fmt"

func binarySearch(arr []int, startIndex, endIndex, value int) int {
	middleElem := (startIndex + (endIndex - 1)) / 2
	if startIndex >= endIndex {
		return -1
	}
	if arr[middleElem] == value {
		return middleElem
	}
	if arr[middleElem] > value {
		return binarySearch(arr, startIndex, middleElem, value)
	}
	if arr[middleElem] < value {
		return binarySearch(arr, middleElem+1, endIndex, value)
	}
	return -1
}

func main() {
	arr := []int{5, 7, 7, 8, 8, 10}
	elmFound := binarySearch(arr, 0, len(arr), 8)
	fmt.Println("IndexFound At: ", elmFound)
}