Search⌘ K
Home
Courses
Data Structures & Algorithms In Go

Solution Review: Binary Search

Learn how to implement and understand binary search in Go for sorted arrays. Discover how the algorithm divides search space effectively, compare elements, and analyze time complexity for efficient searching.

We'll cover the following...

Solution

  • We can use binary search to search effectively when we have data arranged in increasing or decreasing order. We divide our search space in half at each stage.
  • We compare the middle value with the value we’re looking for at each point. We return true if the mid value is equal to the value we’re looking for.
  • If the value is smaller than the middle value, we search the left half of the array (if the array is arranged in ascending order). Otherwise, we search the right half of the array.
  • If we find the value we’re looking for, we return true. Otherwise, we return false.

Solution code

Go (1.6.2)
package main
import "fmt"
func BinarySearch(data []int, value int) bool { 
    var mid int
    low := 0
    high := len(data) - 1
    for low <= high {
        mid = (low + high)/2
        if data[mid] == value { // values find
            return true
        } else {
            if data[mid] < value { // move to left
                low = mid + 1
            } else {
                high = mid - 1   // move to right
            }
        }
    }
  return false                  // value not found 
}
//Testing code
func main() {
    arr := []int{1, 2, 3, 4, 5, 6, 7, 9}
    fmt.Println("BinarySearch:", BinarySearch(arr, 8))
    fmt.Println("BinarySearch:", BinarySearch(arr, 3))
}

Time complexity

Recurrence Relation: T(n)=T(n/2)+1forn>1T(n) = T(n/2) + 1 \quad for \quad n > 1

T(n)=1ifn<=1T(n)= 1 \quad if \quad n <= 1

T(n/2)=T(n/22)+1T(n/2) = T(n/2^{2}) + 1 ...