Binary Search

Definition

Definition

Binary search is an efficient algorithm used to find a target value within a sorted array or list. It works by repeatedly dividing the search interval in half until the target value is found or the interval is empty

Explanation

Start with a sorted array. Find the middle index of the array. If the middle element matches the target, return its index. If the middle element is greater than the target, search the left half, otherwise search the right half. Repeat until the target is found or the search interval is empty

Guidance

• Initialize variables
  • low as the starting index of the array (0) and high as the ending index (length of the array - 1)
• While low is less than or equal to high, continue the search
  • calculate the middle index
    • mid = (low + high) / 2
  • if the middle element is equal to the target value
    • return mid
  • if the middle element is greater than the target value
    • set high = mid - 1 to search the left half
  • if the middle element is less than the target value
    • set low = mid + 1 to search the right half
  • repeat steps in a while loop until low is greater than high, indicating the target value is not present in the array

Tips

• ensure the array is sorted beforehand
• watch out for integer overflow when calculating the midpoint (mid = (low + high) / 2). Consider using mid = low + (high - low) / 2 to avoid this issue
• make sure to handle edge cases such as empty arrays or arrays with only one element
• remember to handle scenarios where the target value is not present in the array

Practice

Practice

binarySearch(arr, target):
  low = 0
  high = length(arr) - 1

  while low <= high:
    mid = (low + high) / 2

    if arr[mid] == target:
      return mid
    elif arr[mid] < target:
      low = mid + 1
    else:
      high = mid - 1

  return -1 // Target not found

Solution

package main

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
}

public class Main {

  public static int binarySearch(int[] arr, int target) {
    int left = 0;
    int 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;
  }
}

function binarySearch(arr, target) {
  let left = 0;
  let 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;
}

fun binarySearch(arr: IntArray, target: Int): Int {
    var left = 0
    var right = arr.size - 1

    while (left <= right) {
        val mid = left + (right - left) / 2

        when {
            arr[mid] == target -> return mid
            arr[mid] < target -> left = mid + 1
            else -> right = mid - 1
        }
    }

    return -1
}

def binary_search(arr, target):
    left, right = 0, len(arr) - 1

    while left <= right:
        mid = left + (right - left) // 2

        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1

fn binary_search(arr: &[i32], target: i32) -> i32 {
    let mut left = 0;
    let mut right = arr.len() - 1;

    while left <= right {
        let mid = left + (right - left) / 2;

        if arr[mid] == target {
            return mid as i32;
        } else if arr[mid] < target {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    -1
}

function binarySearch(arr: number[], target: number): number {
  let left = 0;
  let 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;
}