# encoding: utf-8
# 版權所有 2024 ©塗聚文有限公司
# 許可資訊查看：言語成了邀功的功臣，還需要行爲每日來值班嗎？
# 描述： 主、子表單 窗體傳值  Parent-child form operations
# Author    : geovindu,Geovin Du 塗聚文.
# IDE       : PyCharm 2023.1 python 3.11
# OS        : windows 10
# Datetime  : 2024/10/24 22:09
# User      : geovindu
# Product   : PyCharm
# Project   : IctGame
# File      : ui/main.py
# explain   : 學習

import bisect


def binary_search_bisect(arr:list, x):
    """

    :param arr: 列表
    :param x: 需要找的值
    :return: 返回索引值
    """
    i = bisect.bisect_left(arr, x)
    if i != len(arr) and arr[i] == x:
        return i
    else:
        return -1


def binary_search(arr:list, low, high, x):
    """

    :param arr:列表
    :param low: 0
    :param high: 列表長度 len(arr)
    :param x:需要找的值
    :return:返回索引值
    """
    # Check base case
    if high >= low:

        mid = (high + low) // 2

        # If element is present at the middle itself
        if arr[mid] == x:
            return mid

        # If element is smaller than mid, then it can only
        # be present in left subarray
        elif arr[mid] > x:
            return binary_search(arr, low, mid - 1, x)

        # Else the element can only be present in right subarray
        else:
            return binary_search(arr, mid + 1, high, x)

    else:
        # Element is not present in the array
        return -1



def binary_search2(arr:list, x):
    """
    Iterative Binary Search Function
    It returns index of x in given array arr if present,
    else returns -1
    :param arr: 
    :param x:
    :return:
    """

    low = 0
    high = len(arr) - 1
    mid = 0

    while low <= high:

        mid = (high + low) // 2

        # If x is greater, ignore left half
        if arr[mid] < x:
            low = mid + 1

        # If x is smaller, ignore right half
        elif arr[mid] > x:
            high = mid - 1

        # means x is present at mid
        else:
            return mid

    # If we reach here, then the element was not present
    return -1

def binarysearch3(arr:list,key):
    """
    
    :param arr: 
    :param key: 
    :return: (index, times)
    """
    low=0
    hight=len(arr)-1
    middle=int((hight+low)/2)
    times=0
    while True:
        times+=1
        if key==arr[middle]:
            rtn=middle
            break
        if key>arr[middle]:
            low=middle+1
        else:
            hight=middle-1
        middle=int((hight+low)/2)
        if low>hight:
            rtn=-1
            break
    return rtn,times
    
def sequentialsearch(arr:list,key):
    """
    
    :param arr: 
    :param key: 
    :return: 
    """
    if len(arr)>0:
        for i in range(len(arr)):
            if arr[i]==key:
                return i
        return -1
    
# Test array
# 1
arr = [2, 3, 4, 10, 40]
x = 10

# Function call
result = binary_search_bisect(arr, x)

if result != -1:
    print("Element is present at index", str(result))
else:
    print("Element is not present in array")
# 2
# Function call
result = binary_search(arr, 0, len(arr) - 1, x)

if result != -1:
    print("Element is present at index", str(result))
else:
    print("Element is not present in array")

# 3
# Test array
arr = [2, 3, 4, 10, 40]
x = 10

# Function call
result = binary_search2(arr, x)

if result != -1:
    print("Element is present at index", str(result))
else:
    print("Element is not present in array")
    
# 4
sorteddata=sorted(arr)
index,times=binarysearch3(sorteddata,x)
if index!=-1:
    print(f"Element is present at index {index} finde times:{times}")
else:
    print('no search')
    
# 5
se=sequentialsearch(arr,x)
if se!=-1:
    print("Element is present at index", str(se))
else:
    print("Element is not present in array")