what is the time complexity code for binary search in all different coding languages
- User
what is the time complexity code for binary search in all different coding languages
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 foundJava
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 endGo
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.
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.