Skip to content
TheChatArchiveThe Chat Archive
Mistralmistral-small-3.1-24b-instruct-2503· Mistral AIHugging Face LMArena Human Preference 140K

what is the time complexity code for binary search in all different coding languages

From a Chatbot Arena battleThe same person sent this prompt to two anonymous models at once. Compare it with o3-mini’s answer.
  1. User

    what is the time complexity code for binary search in all different coding languages

  2. Mistral Assistant

    Binary search is a classic algorithm for finding the position of a target value within a sorted array. The time complexity of binary search is (O(\log n)), where (n) is the number of elements in the array. This is because the algorithm repeatedly divides the search interval in half.

    Below are examples of binary search implementations in several popular programming languages, along with a brief explanation of the code:

    Python

    def binary_search(arr, target):
        left, right = 0, len(arr) - 1
        while left <= right:
            mid = (left + right) // 2
            if arr[mid] == target:
                return mid
            elif arr[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        return -1  # Target not found
    

    Java

    public class BinarySearch {
        public static int binarySearch(int[] arr, int target) {
            int left = 0, right = arr.length - 1;
            while (left <= right) {
                int mid = left + (right - left) / 2;
                if (arr[mid] == target) {
                    return mid;
                } else if (arr[mid] < target) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
            return -1;  // Target not found
        }
    }
    

    C++

    #include <iostream>
    #include <vector>
    
    int binarySearch(const std::vector<int>& arr, int target) {
        int left = 0, right = arr.size() - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] == target) {
                return mid;
            } else if (arr[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1;  // Target not found
    }
    

    JavaScript

    function binarySearch(arr, target) {
        let left = 0, right = arr.length - 1;
        while (left <= right) {
            let mid = Math.floor((left + right) / 2);
            if (arr[mid] === target) {
                return mid;
            } else if (arr[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1;  // Target not found
    }
    

    C#

    public class BinarySearch {
        public static int BinarySearch(int[] arr, int target) {
            int left = 0, right = arr.Length - 1;
            while (left <= right) {
                int mid = left + (right - left) / 2;
                if (arr[mid] == target) {
                    return mid;
                } else if (arr[mid] < target) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
            return -1;  // Target not found
        }
    }
    

    Ruby

    def binary_search(arr, target)
      left, right = 0, arr.length - 1
      while left <= right
        mid = (left + right) / 2
        if arr[mid] == target
          return mid
        elsif arr[mid] < target
          left = mid + 1
        else
          right = mid - 1
        end
      end
      return -1  # Target not found
    end
    

    Go

    package main
    
    import "fmt"
    
    func binarySearch(arr []int, target int) int {
        left, right := 0, len(arr)-1
        for left <= right {
            mid := left + (right-left)/2
            if arr[mid] == target {
                return mid
            } else if arr[mid] < target {
                left = mid + 1
            } else {
                right = mid - 1
            }
        }
        return -1  // Target not found
    }
    
    func main() {
        arr := []int{1, 2, 3, 4, 5}
        target := 3
        fmt.Println(binarySearch(arr, target))  // Output: 2
    }
    

    Swift

    func binarySearch(arr: [Int], target: Int) -> Int {
        var left = 0
        var right = arr.count - 1
        while left <= right {
            let mid = left + (right - left) / 2
            if arr[mid] == target {
                return mid
            } else if arr[mid] < target {
                left = mid + 1
            } else {
                right = mid - 1
            }
        }
        return -1  // Target not found
    }
    

    Rust

    fn binary_search(arr: &[i32], target: i32) -> i32 {
        let mut left = 0;
        let mut right = arr.len() as i32 - 1;
        while left <= right {
            let mid = left + (right - left) / 2;
            if arr[mid as usize] == target {
                return mid;
            } else if arr[mid as usize] < target {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        -1  // Target not found
    }
    
    fn main() {
        let arr = [1, 2, 3, 4, 5];
        let target = 3;
        println!("{}", binary_search(&arr, target));  // Output: 2
    }
    

    In all these examples, the time complexity remains (O(\log n)) due to the halving of the search interval in each iteration.

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.

Identical first prompt