Let’s play a number guessing game. Pick an integer between 1 and 100 — you have to guess the number in my head, and you must do it in the fewest guesses possible. How would you approach it?
The answer is simple: you’d start by guessing 50. If it’s wrong and too high, you’d guess 25 next. If too low, you’d guess 75. And so on — each time you split the remaining range in half. What you’re using is essentially Binary Search.
Concept
Binary Search: Before using this algorithm, the list being searched must be sorted first. If the element you’re looking for is in the list, binary search returns the position of that element; otherwise, it returns -1.
Complexity
- Time complexity: O(log n)
- Space complexity: O(1)
Examples
Go
package main
import "fmt"
func binarySearch(list []int, target int) int {
low := 0
high := len(list) - 1
for low <= high {
mid := (low + high) / 2
if list[mid] == target {
return mid
} else if list[mid] < target {
low = mid + 1
} else {
high = mid - 1
}
}
return -1
}
func main() {
fmt.Println(binarySearch([]int{1, 2, 3, 4, 5}, 3)) // 2
fmt.Println(binarySearch([]int{1, 2, 3, 4, 5}, 6)) // -1
}
C#
class Algorithm
{
public static int binarySearch(int[] list, int target)
{
var low = 0;
var high = list.Length - 1;
while(low <= high)
{
var mid = (low + high) / 2;
if (list[mid] == target)
{
return mid;
}
if (list[mid] < target)
{
low = mid + 1;
}
else
{
high = mid - 1;
}
}
return -1;
}
public static void Main(String[] args)
{
Console.WriteLine(binarySearch(new int[] {1, 2, 3, 4, 5}, 3)); // 2
Console.WriteLine(binarySearch(new int[] {1, 2, 3, 4, 5}, 6)); // -1
}
}
Feel free to leave a comment on my blog. Your feedback motivates me to keep writing. Thank you for reading, and let’s grow together to become better versions of ourselves.
