Binary Search

def search_rotated(nums: list[int], target: int) -> int:
    """Index of `target` in a rotated sorted array of distinct values, or -1."""
    lo, hi = 0, len(nums) - 1  # Closed [lo, hi]: we return as soon as mid matches.
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if nums[mid] == target:
            return mid
        if nums[lo] <= nums[mid]:
            # The left half nums[lo..mid] is sorted. Keep it only if target fits in it.
            if nums[lo] <= target < nums[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        else:
            # The right half nums[mid..hi] is sorted. Keep it only if target fits in it.
            if nums[mid] < target <= nums[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1


if __name__ == "__main__":
    print(search_rotated([4, 5, 6, 7, 0, 1, 2], 0))  # 4
    print(search_rotated([4, 5, 6, 7, 0, 1, 2], 3))  # -1
    print(search_rotated([1], 0))  # -1
    print(search_rotated([5, 1, 3], 3))  # 2

// Index of `target` in a rotated sorted array of distinct values, or -1.
export function searchRotated(nums: number[], target: number): number {
  let lo = 0;
  let hi = nums.length - 1; // Closed [lo, hi]: we return as soon as mid matches.
  while (lo <= hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (nums[mid] === target) return mid;
    if (nums[lo] <= nums[mid]) {
      // The left half nums[lo..mid] is sorted. Keep it only if target fits in it.
      if (nums[lo] <= target && target < nums[mid]) hi = mid - 1;
      else lo = mid + 1;
    } else {
      // The right half nums[mid..hi] is sorted. Keep it only if target fits in it.
      if (nums[mid] < target && target <= nums[hi]) lo = mid + 1;
      else hi = mid - 1;
    }
  }
  return -1;
}

console.log(searchRotated([4, 5, 6, 7, 0, 1, 2], 0)); // 4
console.log(searchRotated([4, 5, 6, 7, 0, 1, 2], 3)); // -1
console.log(searchRotated([1], 0)); // -1
console.log(searchRotated([5, 1, 3], 3)); // 2

package main

import "fmt"

// searchRotated returns the index of target in a rotated sorted array of
// distinct values, or -1.
func searchRotated(nums []int, target int) int {
	lo, hi := 0, len(nums)-1 // Closed [lo, hi]: we return as soon as mid matches.
	for lo <= hi {
		mid := lo + (hi-lo)/2
		if nums[mid] == target {
			return mid
		}
		if nums[lo] <= nums[mid] {
			// The left half nums[lo..mid] is sorted. Keep it only if target fits in it.
			if nums[lo] <= target && target < nums[mid] {
				hi = mid - 1
			} else {
				lo = mid + 1
			}
		} else {
			// The right half nums[mid..hi] is sorted. Keep it only if target fits in it.
			if nums[mid] < target && target <= nums[hi] {
				lo = mid + 1
			} else {
				hi = mid - 1
			}
		}
	}
	return -1
}

func main() {
	fmt.Println(searchRotated([]int{4, 5, 6, 7, 0, 1, 2}, 0)) // 4
	fmt.Println(searchRotated([]int{4, 5, 6, 7, 0, 1, 2}, 3)) // -1
	fmt.Println(searchRotated([]int{1}, 0))                   // -1
	fmt.Println(searchRotated([]int{5, 1, 3}, 3))             // 2
}

using System;

public class Solution
{
    // Index of target in a rotated sorted array of distinct values, or -1.
    public static int SearchRotated(int[] nums, int target)
    {
        int lo = 0, hi = nums.Length - 1; // Closed [lo, hi]: we return as soon as mid matches.
        while (lo <= hi)
        {
            int mid = lo + (hi - lo) / 2;
            if (nums[mid] == target) return mid;
            if (nums[lo] <= nums[mid])
            {
                // The left half nums[lo..mid] is sorted. Keep it only if target fits in it.
                if (nums[lo] <= target && target < nums[mid]) hi = mid - 1;
                else lo = mid + 1;
            }
            else
            {
                // The right half nums[mid..hi] is sorted. Keep it only if target fits in it.
                if (nums[mid] < target && target <= nums[hi]) lo = mid + 1;
                else hi = mid - 1;
            }
        }
        return -1;
    }

    public static void Main()
    {
        Console.WriteLine(SearchRotated(new[] { 4, 5, 6, 7, 0, 1, 2 }, 0)); // 4
        Console.WriteLine(SearchRotated(new[] { 4, 5, 6, 7, 0, 1, 2 }, 3)); // -1
        Console.WriteLine(SearchRotated(new[] { 1 }, 0)); // -1
        Console.WriteLine(SearchRotated(new[] { 5, 1, 3 }, 3)); // 2
    }
}

public class Solution {
    // Index of target in a rotated sorted array of distinct values, or -1.
    static int searchRotated(int[] nums, int target) {
        int lo = 0, hi = nums.length - 1; // Closed [lo, hi]: we return as soon as mid matches.
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (nums[mid] == target) return mid;
            if (nums[lo] <= nums[mid]) {
                // The left half nums[lo..mid] is sorted. Keep it only if target fits in it.
                if (nums[lo] <= target && target < nums[mid]) hi = mid - 1;
                else lo = mid + 1;
            } else {
                // The right half nums[mid..hi] is sorted. Keep it only if target fits in it.
                if (nums[mid] < target && target <= nums[hi]) lo = mid + 1;
                else hi = mid - 1;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        System.out.println(searchRotated(new int[] {4, 5, 6, 7, 0, 1, 2}, 0)); // 4
        System.out.println(searchRotated(new int[] {4, 5, 6, 7, 0, 1, 2}, 3)); // -1
        System.out.println(searchRotated(new int[] {1}, 0)); // -1
        System.out.println(searchRotated(new int[] {5, 1, 3}, 3)); // 2
    }
}

def min_eating_speed(piles: list[int], h: int) -> int:
    """Slowest whole-number speed that lets Koko eat every pile within `h` hours."""
    lo, hi = 1, max(piles)  # At max(piles) every pile takes one hour.
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if hours_needed(piles, mid) <= h:
            hi = mid  # Fast enough: the answer is mid or slower.
        else:
            lo = mid + 1  # Too slow, and so is every speed below mid.
    return lo


def hours_needed(piles: list[int], speed: int) -> int:
    """Hours to finish every pile at `speed` bananas per hour."""
    # Round up: a partly eaten pile still costs a whole hour.
    return sum((pile + speed - 1) // speed for pile in piles)


if __name__ == "__main__":
    print(min_eating_speed([3, 6, 7, 11], 8))  # 4
    print(min_eating_speed([30, 11, 23, 4, 20], 5))  # 30
    print(min_eating_speed([30, 11, 23, 4, 20], 6))  # 23

// Slowest whole-number speed that lets Koko eat every pile within `h` hours.
export function minEatingSpeed(piles: number[], h: number): number {
  let lo = 1;
  let hi = Math.max(...piles); // At max(piles) every pile takes one hour.
  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (hoursNeeded(piles, mid) <= h) hi = mid; // Fast enough: the answer is mid or slower.
    else lo = mid + 1; // Too slow, and so is every speed below mid.
  }
  return lo;
}

// Hours to finish every pile at `speed` bananas per hour.
function hoursNeeded(piles: number[], speed: number): number {
  let hours = 0;
  // Round up: a partly eaten pile still costs a whole hour.
  for (const pile of piles) hours += Math.ceil(pile / speed);
  return hours;
}

console.log(minEatingSpeed([3, 6, 7, 11], 8)); // 4
console.log(minEatingSpeed([30, 11, 23, 4, 20], 5)); // 30
console.log(minEatingSpeed([30, 11, 23, 4, 20], 6)); // 23

package main

import (
	"fmt"
	"slices"
)

// minEatingSpeed returns the slowest whole-number speed that lets Koko eat
// every pile within h hours.
func minEatingSpeed(piles []int, h int) int {
	lo, hi := 1, slices.Max(piles) // At max(piles) every pile takes one hour.
	for lo < hi {
		mid := lo + (hi-lo)/2
		if hoursNeeded(piles, mid) <= h {
			hi = mid // Fast enough: the answer is mid or slower.
		} else {
			lo = mid + 1 // Too slow, and so is every speed below mid.
		}
	}
	return lo
}

// hoursNeeded returns the hours to finish every pile at speed bananas per hour.
func hoursNeeded(piles []int, speed int) int {
	hours := 0
	for _, pile := range piles {
		// Round up: a partly eaten pile still costs a whole hour.
		hours += (pile + speed - 1) / speed
	}
	return hours
}

func main() {
	fmt.Println(minEatingSpeed([]int{3, 6, 7, 11}, 8))       // 4
	fmt.Println(minEatingSpeed([]int{30, 11, 23, 4, 20}, 5)) // 30
	fmt.Println(minEatingSpeed([]int{30, 11, 23, 4, 20}, 6)) // 23
}

using System;
using System.Linq;

public class Solution
{
    // Slowest whole-number speed that lets Koko eat every pile within h hours.
    public static int MinEatingSpeed(int[] piles, int h)
    {
        int lo = 1;
        int hi = piles.Max(); // At max(piles) every pile takes one hour.
        while (lo < hi)
        {
            int mid = lo + (hi - lo) / 2;
            if (HoursNeeded(piles, mid) <= h) hi = mid; // Fast enough: the answer is mid or slower.
            else lo = mid + 1; // Too slow, and so is every speed below mid.
        }
        return lo;
    }

    // Hours to finish every pile at speed bananas per hour. A long, because
    // slow speeds over many big piles overflow an int.
    static long HoursNeeded(int[] piles, int speed)
    {
        long hours = 0;
        // Round up: a partly eaten pile still costs a whole hour.
        foreach (int pile in piles) hours += (pile + speed - 1) / speed;
        return hours;
    }

    public static void Main()
    {
        Console.WriteLine(MinEatingSpeed(new[] { 3, 6, 7, 11 }, 8)); // 4
        Console.WriteLine(MinEatingSpeed(new[] { 30, 11, 23, 4, 20 }, 5)); // 30
        Console.WriteLine(MinEatingSpeed(new[] { 30, 11, 23, 4, 20 }, 6)); // 23
    }
}

import java.util.Arrays;

public class Solution {
    // Slowest whole-number speed that lets Koko eat every pile within h hours.
    static int minEatingSpeed(int[] piles, int h) {
        int lo = 1;
        int hi = Arrays.stream(piles).max().getAsInt(); // At max(piles) every pile takes one hour.
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (hoursNeeded(piles, mid) <= h) hi = mid; // Fast enough: the answer is mid or slower.
            else lo = mid + 1; // Too slow, and so is every speed below mid.
        }
        return lo;
    }

    // Hours to finish every pile at speed bananas per hour. A long, because
    // slow speeds over many big piles overflow an int.
    static long hoursNeeded(int[] piles, int speed) {
        long hours = 0;
        // Round up: a partly eaten pile still costs a whole hour.
        for (int pile : piles) hours += (pile + speed - 1) / speed;
        return hours;
    }

    public static void main(String[] args) {
        System.out.println(minEatingSpeed(new int[] {3, 6, 7, 11}, 8)); // 4
        System.out.println(minEatingSpeed(new int[] {30, 11, 23, 4, 20}, 5)); // 30
        System.out.println(minEatingSpeed(new int[] {30, 11, 23, 4, 20}, 6)); // 23
    }
}