###### tags: `Week_1`, `Binary Search`

# Binary Search

## [704. Binary Search](https://leetcode.com/problems/binary-search/)

harry

# @param {Integer[]} nums
# @param {Integer} target
# @return {Integer}
def search(nums, target)
  front = 0
  back = nums.size - 1

  loop do
    mid = (front + back)/2

    if nums[mid] == target
      return mid
    else
      if front >= back
        break
      elsif target > nums[mid]
        front = mid+1
      else
        back = mid-1
      end
    end
  end

  return -1
end

beny(t=n):

public class Solution {
    public int Search(int[] nums, int target) {
        for(int i = 0; i < nums.Count(); i++){
            if(nums[i] == target){
                return i;
            }
        }
        return -1;
    }
}

beny:

public class Solution {
    public int Search(int[] nums, int target) {
        int left = 0;
        int right = nums.Length - 1;
        while(left <= right){
            int mid = (left + right) / 2;
            if(nums[mid] > target){
                right = mid - 1;
            }else if(nums[mid] < target){
                left = mid + 1;
            }else{
                return mid;
            }
        }
        return -1;
    }
}

Sam:

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        
        start = 0
        end = len(nums) - 1
        
        while start <= end:
            mid = (start + end) // 2

            if nums[mid] == target:
                return mid
            elif nums[mid] > target:
                end = mid - 1
            else:
                start = mid + 1
        
        return -1
        

## [278. First Bad Version](https://leetcode.com/problems/first-bad-version/)
harry

def first_bad_version(n)
  front = 1
  back = n
  versions = {}

  loop do
    mid = (front + back)/2
    bad = is_bad_version(mid)
    versions[mid] = bad
    
    if front >= back
      if versions[mid] == false
        return mid+1
      else
        return mid
      end
    end

    if bad
      if versions[mid-1] == false
        return mid
      else
        back = mid-1
      end
    else
      front = mid+1
    end
  end
end

beny:

public class Solution : VersionControl {
    public int FirstBadVersion(int n) {     
        int left = 1;
        int right = n;
        while (left < right){
            int mid = left + (right - left) / 2;          
            if(!IsBadVersion(mid)){
                left = mid + 1;
            }else{
                right = mid;          
            }                               
        }      
        return left;
    }
}

Sam:

# The isBadVersion API is already defined for you.
# def isBadVersion(version: int) -> bool:

class Solution:
    def firstBadVersion(self, n: int) -> int:
        
        start = 1
        end = n
        
        if isBadVersion(1) is True:
            return 1
        
        temp_map = dict()
        while start <= end:
            mid = (start + end) // 2
            
            if mid in temp_map:
                if temp_map[mid] and not temp_map[mid-1]:
                    return mid
                elif temp_map[mid] and temp_map[mid-1]:
                    end = mid - 1
                else:
                    start = mid + 1
            else:
                temp_map[mid] = isBadVersion(mid)
                temp_map[mid - 1] = isBadVersion(mid - 1)