Data Structures & Algorithms In Go/

...

/

Solution Review: Binary Search

Solution Review: Binary Search

Let’s take a detailed look at the previous challenge’s solution.

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

Press + to interact
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)+ ...